#include<iostream>
#include<algorithm>
#include<string>
#include<string.h>
#include<cmath>
#define rep(i,a,b) for(ll i=a;i<=b;++i)
#define per(i,a,b) for(ll i=a;i>=b;--i)
#define fi first
#define se second
#define mp make_pair
#define all(x) x.begin(),x.end()
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const ll maxn=6e1+10,inf=0x3f3f3f3f3f3f3f3f;

ull maxbase[maxn];
void Init(){
	maxbase[1]=1e18;
	maxbase[2]=1e18;
	rep(i,3,60){
		int j=i-1;
		maxbase[i]=pow(1e18,1.0/j);
		while(pow((maxbase[i]+1)*1.0,j)<=1e18) maxbase[i]++;
		//cout<<i<<' '<<pow(maxbase[i]*1.0,j*1.0)<<endl;
	}
}

string X; ull M;
bool Check(ll b){
	
	ull tp=1,temp=0;
	per(i,X.size()-1,0) {	
		temp+=(X[i]-'0')*tp;
		tp*=b;
		if(temp>M) return 0;
	}
	return 1;
}
int main()
{
	Init();
	cin>>X;
	cin>>M;

	if(X.size()==1){ cout<<(X[0]-'0'<=M?1:0)<<endl;return 0;}
	int large=0;
	rep(i,0,X.size()-1) large=max(large,X[i]-'0');
	
	ull l=large,r=maxbase[X.size()];
	while(l<r){
		ll mid=(l+r)/2+1;
		if(Check(mid)) l=mid;
		else r=mid-1;
	}
	cout<<l-large<<endl;
	return 0;
}
#include <bits/stdc++.h>
#define ll long long
using namespace std;

int main() {
    string X;
    ll M;
    cin >> X >> M;
    int d = 0;
    for (char c : X) if (c-'0'>d) d = c-'0';
    if (X.size() == 1) {
        cout << (d<=M) << endl;
        return 0;
    }
    ll L = d, R = M +1;
    while (R-L>1) {
        ll mid = (L+R)/2;
        bool ng = false;
        ll now = 0;
        for (char c : X) {
            if (now > M/mid) {ng = true; break;}
            now = now * mid + (c - '0');
        }
        if (ng | now > M) R = mid;
        else L = mid;
    }
    cout << L-d << endl;
}
// copy https://atcoder.jp/contests/abc192/submissions/20364184