#include<algorithm>
#include<bitset>
#include<cmath>
#include<complex>
#include<deque>
#include<functional>
#include<iomanip>
#include<iostream>
#include<map>
#include<numeric>
#include<queue>
#include<set>
#include<stack>
#include<string>
#include<unordered_map>
#include<unordered_set>
#include<utility>
#include<vector>

using namespace std;
typedef long long ll;

#define REP(i, n) for(ll i=0;i<(ll)(n);i++)
#define RREP(i, n) for(ll i=(ll)(n-1);i>=0;i--)
#define FOR(i, a, b) for(ll i=(ll)(a); i<=(ll)(b); i++)
#define RFOR(i, a, b) for(ll i=(ll)(a);i>=(ll)(b); i--)
#define ALL(x) (x).begin(),(x).end()
#define SIZE(x) ((ll)(x).size())
#define INF 1000000000000
#define MOD 1000000007 // 10^9+7
#define PB push_back
#define MP make_pair
#define F first
#define S second

ll binsearch(ll d, ll M, vector<int> X){
	ll mind = d+1;
	ll maxd = 1000000000000000001;
	{
		ll num=0;
		for(auto c : X){
			//if(M/(double)r - c< num/(double)r ){
			if((M-c)/(double)mind<num){
				return 0;
			}
			num *= mind;
			num += c;
		}
	}
	while(true){
loop:
		ll newd = (mind+maxd)/2;
		ll num = 0;
		for(auto c : X){
			//if(M/(double)c - r < num/(double)c){
			if((M-c)/(double)newd<num){
				maxd = newd;
				goto loop;
			}
			num *= newd;
			num += c;
		}
		if(mind == newd)break;
		mind = newd;
	}
	return mind - d;
}

signed main()
{
	string X;
	ll M;
	cin >> X;
	cin >> M;
	if(X.size() == 1){
		if(X[0]-'0'>M){
			cout << 0;
		}else{
			cout << 1;
		}
		cout << endl;
		return 0;
	}
	int d = 0;
	vector<int> vecX;
	for(char c : X){
		vecX.PB(c-'0');
		if(d < c-'0'){
			d = c-'0';
		}
	}
	cout << binsearch(d, M, vecX) << endl;
}

#include <cstdlib>
#include <cctype>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>
#include <string>
#include <iostream>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <list>

using namespace std;

#define PB push_back
#define MP make_pair

#define REP(i,n) for(i=0;i<(n);++i)
#define PER(i,n) for(i=(n - 1);i>=0;--i)
#define FOR(i,l,h) for(i=(l);i<=(h);++i)
#define FORD(i,h,l) for(i=(h);i>=(l);--i)
#define mod 1000000007
#define maxInt 2147483647
#define minInt -2147483648
#define maxLL 9223372036854775807
#define minLL -9223372036854775807

typedef vector<int> VI;
typedef vector<string> VS;
typedef vector<double> VD;
typedef long long LL;
typedef unsigned long long ULL;
typedef __int128 l128;
typedef pair<int,int> PII;
typedef map<int, int> MII;

int check(ULL n, string x, LL m)
{
    l128 res = 0;
    for(int i = 0; i < x.size(); i++)
    {
        res = res * n + l128(x[i] - '0');
        if(res > m) return 0;
    }

    return 1;
}

int main()
{
    string x;
    ULL m, i;
    while(cin>>x)
    {
        cin>>m;
        if(x.size() == 1)
        {
            if(x[0] - '0' - 1 <= m) cout<<1<<endl;
            else cout<<0<<endl;
        }
        else{
            int maxdig = 0;
            REP(i, x.size()) maxdig = max(maxdig, x[i] - '0');
            ULL l = 0, r = 1e18, mid;
            while(l < r)
            {
                mid = (l + r +1)/2;
                if(check(mid,x, m) == 1) l = mid;
                else r = mid -1;
            }

            if(l <= maxdig ) cout<<0<<endl;
            else cout<<l - maxdig<<endl;
        }
    }
    return 0;
}
