#include<bits/stdc++.h>
using namespace std;
#define debug(...) fprintf(stderr, __VA_ARGS__), fflush(stderr)
typedef __int128 ll;
typedef long double ld;
typedef pair<ll,ll> p2;
#define sz(a) ll(a.size())
std::ostream&
operator<<( std::ostream& dest, __int128_t value )
{
    std::ostream::sentry s( dest );
    if ( s ) {
        __uint128_t tmp = value < 0 ? -value : value;
        char buffer[ 128 ];
        char* d = std::end( buffer );
        do
        {
            -- d;
            *d = "0123456789"[ tmp % 10 ];
            tmp /= 10;
        } while ( tmp != 0 );
        if ( value < 0 ) {
            -- d;
            *d = '-';
        }
        int len = std::end( buffer ) - d;
        if ( dest.rdbuf()->sputn( d, len ) != len ) {
            dest.setstate( std::ios_base::badbit );
        }
    }
    return dest;
}
ll f(string s,ll x,ll m){
	ll sum=0,p=1;
	for(ll i=0;i<sz(s);i++){
		ll val=(s[i]-'0');
		sum+=val*p;
		if(sum>m)
			return 0;
		p*=x;
		if(i<sz(s)-1&&p>m)
			return 0;
	}
	return 1;
}
void solve(){
	string s;
	long long int tr;
	cin>>s>>tr;
	ll m=tr;
	ll d=0;
	for(ll i=0;i<sz(s);i++)
		d=max(d,ll(s[i]-'0'));
	reverse(s.begin(),s.end());
	ll l0=d+1,r0=1000000000000000000; 
	while(l0<=r0){
		ll m0=(l0+r0)/2;
		if(f(s,m0,m))
			l0=m0+1;
		else
			r0=m0-1;
	}
	ll res=max(ll(0),r0-d);
	if(sz(s)==1){
		res=min(res,ll(1));
	}
	cout<<(long long int)(res);
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    #ifndef ONLINE_JUDGE
    freopen("input.txt", "r" , stdin);
    freopen("output.txt", "w", stdout);
    #endif
    clock_t z=clock();
    ll qc=1;
    //cin>>qc;
    for(ll i=1;i<=qc;i++){
    	solve();
    }
    debug("Total Time:%.4Lf\n",(ld)(clock()-z)/CLOCKS_PER_SEC);
}
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <cmath>
#include <queue>
#include <map>
using namespace std;
using ll = long long int;
using P = pair<int, int>;

int main(){
    string x;
    ll m;
    cin >> x;
    reverse(x.begin(), x.end());
    cin >> m;
    int basemin = 0;
    for(auto &p: x) basemin = max(basemin, p-'0');
    basemin++;

    if(x.length() == 1){
        if(x[0]-'0' <= m) cout << 1 << endl;
        else cout << 0 << endl;
    }else{
        ll ans = 0;
        ll ac = 2;
        ll wa = 1'000'000'000'000'000'000LL + 1LL;
        while(wa-ac > 1){
            ll mid = (wa+ac)/2;
            ll sum = 0;
            ll base = 1;
            if(mid < basemin){
                ac = mid;
                continue;
            }
            bool iswa = false;
            sum += x[0]-'0';
            if(sum > m) iswa = true;
            for(int i = 1; i < x.length(); i++){
                if(base > m/mid){
                    iswa = true;
                    break;
                }
                base *= mid;
                //sum += base*(x[i]-'0');
                if((x[i]-'0') <= (m-sum)/base){
                    sum += base*(x[i]-'0');
                }else{
                    iswa = true;
                    break;
                }
            }
            if(iswa) wa = (ll)mid;
            else ac = (ll)mid;
        }
        cout << max(0LL, ac-basemin+1) << endl;
    }

    return 0;
}