#include<bits/stdc++.h>
using namespace std;
#define int long long
#define double long double
#define endl '\n'
#define pb push_back
#define pob pop_back
#define pii pair<int,int>
// int mod = 3;
#define mod 1000000007
// #define mod 1000000009
// #define mod 163577857
// #define mod 998244353
#define rep(i,n) for (int i = 0; i < n; i++)
#define repp(i,a,b) for(int i = a ; i<b ; i++)
#define reppr(i,a,b) for(int i = a-1 ; i>=b ; i--)
#define repr(i,n) for (int i = n - 1; i >= 0; i--)
#define ff first
#define ss second
#define inf 9223372036854775807
#define infn -9223372036854775807
#define pi 3.14159265358979323846
#define eps 0.0000000001
#define setprec(x) cout << fixed << setprecision(x);
#define REVERSE(a) reverse(all(a));
#define SORT(a) sort(all(a));
#define all(n) n.begin(),n.end()
#define setbits(x) __builtin_popcountll(x)
 
//GCD and LCM
    int gcd (int a, int b) { return b ? gcd (b, a % b) : a; }
    int lcm (int a, int b) { return a / gcd(a, b) * b; }

//Modular Exponentiation
    int powmod(int x,int y)
    {
        if (y == 0) return 1;
        int p = powmod(x, y/2) % mod;
        p = (p * p) % mod;
        return (y%2 == 0)? p : (x * p) % mod;
    }
 
//Modular Inverse
    int inverse(int a)
    {
       return powmod(a,mod-2);
    }

////////////////////////////////////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////NO TEXT ABOVE IT//////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////////////////////////////////////

bool codejam = 0, testcases = 0;

int parent[400001];
int rank[400001];
int find_set(int v) {
    if (v == parent[v])
        return v;
    return find_set(parent[v]);
}

void union_sets(int a, int b) {
    a = find_set(a);
    b = find_set(b);
    if (a != b)
        parent[b] = a;
}


void solve()
{
    int n , a , b;
    cin >> n;    
    map<int,vector<int>> m;
    repp(i,1,400001)
        parent[i] = i;
    rep(i,n)
    {
        cin >> a >> b;
        if(a>b) swap(a,b);
        m[a].pb(b);
    }
    set<int> ans;
    for(auto i : m)
    {
        for(auto j : i.ss)
        {
            if(ans.find(find_set(j))==ans.end())
                ans.insert(find_set(j)) , union_sets(i.ff,j);
            else
                ans.insert(find_set(i.ff));
        }
    }
    cout << ans.size() << endl;
}

////////////////////////////////////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////NO TEXT BELOW IT//////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////////////////////////////////////
 
signed main()
{
    ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
    int t = 1;
    if(testcases) 
        cin >> t;
    rep(i,t)
    {
        if(codejam)
            cout << "Case #" << i+ 1<< ": ";
        solve();
    }
}   
#include <bits/stdc++.h>
using namespace std;

vector<long long> base_n(long long n, long long M){
    vector<long long> basen;
    while(M>0){
        basen.push_back(M%n);
        M/=n;
    }
    return basen;
}

int check(long long n, long long M, string X){
    vector<long long> basen = base_n(n,M);
    int ketasuu = basen.size();
    if(ketasuu>X.size()){
        return 1;
    }else if(ketasuu<X.size()){
        return 0;
    }else if(ketasuu==X.size()){
        for(int j=0;j<X.size();j++){
            if(basen[ketasuu-j-1]>X[j]-'0'){
                return 1;
            }else if(basen[ketasuu-j-1]<X[j]-'0'){
                return 0;
            }
        }
        return 2;
    }
    return -1;
}

int main(){
    string X;
    long long M;
    cin >> X >> M;
    int digit_max = 0;
    for(int i=0;i<X.size();i++){
        digit_max = max(digit_max, X[i] - '0');
    }
    long long ans = 0;
    long long start = digit_max;
    long long right = M+1;
    long long left = start;
    long long mid = (left+right)/2;
    if(X.size()==1){
        if((X[0] - '0')<=M){
            ans=1;
        }else{
            ans=0;
        }
    }
    else{
        while(left+1<right){
            mid = (left+right)/2;
            //cout << mid << endl;
            if(check(mid,M,X)==1){
                left = mid;
            }else if(check(mid,M,X)==0){
                right = mid;
            }else if(check(mid,M,X)==2){
                left = mid;
            }
        }
        ans = left-start;
    }
    cout << ans << endl;
}
