#include <bits/stdc++.h>
#define DimMax 1005

using namespace std;

ifstream fin("poarta.in");
ofstream fout("poarta.out");

int c;
int n;
int v[DimMax];
long long nrdalecalca, nrpicaturi;
char ch;

int nrcif(int n)
{
    int nr = 0;
    while(n > 0)
    {
        nr++;
        n /= 10;
    }
    return nr;
}

bool Emaimare(int v[], int n)
{
    if(v[0] > nrcif(n)) return true;
    else if(v[0] < nrcif(n)) return false;
    else
    {
        int nr = 0;
        for(int i = 1;i <= v[0];i++) nr = nr * 10 + v[i];
        if(nr > n) return true;
        else return false;
    }
}

void Imparte(int x)
{
    int rest = 0, val = 0;
    for(int i = 1;i <= v[0];i++)
    {
        val = rest * 10 + v[i];
        rest = val % x;
        v[i] = val / x;
    }
    reverse(v + 1,v + v[0] + 1);
    while(v[v[0]] == 0) v[0]--;
    reverse(v + 1,v + v[0] + 1);
}

void Scade(int x)
{
    int t = 0, val = 0;
    int a[DimMax];
    a[0] = 1; a[1] = 1;
    for(int i = 2;i <= v[0];i++) a[i] = 0;
    for(int i = 1;i <= v[0];i++)
    {
        val = v[i] - a[i] - t;
        if(val < 0)
        {
            val += 10;
            t = 1;
        }else t = 0;
        v[i] = val % 10;
    }
    while(v[v[0]] == 0) v[0]--;
}
int main()
{
    fin>>c;
    fin>>n;
    while(fin>>ch)
    {
        v[++v[0]] = ch - '0';
    }
    nrdalecalca = 1;
    while(Emaimare(v, n))
    {
        if(v[0] <= 6)
        {
            int nr = 0;
            for(int i = 1;i <= v[0];i++) nr = nr * 10 + v[i];
            if(nr == n + 1)
            {
                nrdalecalca++;
                nrpicaturi++;
                break;
            }
        }
        if(v[v[0]] % 2 == 1)
        {
            reverse(v + 1,v + v[0] + 1);
            Scade(1);
            reverse(v + 1,v + v[0] + 1);
            nrdalecalca++;
            nrpicaturi++;
        }
        else
        {
            Imparte(2);
            nrdalecalca++;
            nrpicaturi += 2;
        }
    }
    if(c == 1)
        fout<<nrdalecalca;
    else fout<<nrpicaturi;
    return 0;
}