/*
problem :
algorithm :
created : Programmer_juruo
*/
 
#include <bits/stdc++.h>
using namespace std;
 
#define int unsigned long long
#define N 100005
#define lowbit(x) x & (-x)
#define Rep2(i, n) for(int i = 1; i <= n; i++)
#define rep(i, a, n) for(int i = a; i <= n; i++)
#define Rep(i, n) for(int i = 0; i < n; i++)
#define dbg(x) cout << #x << ":" << x << endl;
#define Se second
#define Fi first
#define Mp make_pair
#define Pb push_back
typedef pair<int, int> Pii;
typedef priority_queue<int> Pq;
typedef long long ll;
 
int n, m;
 
inline ll Read() {
	ll y = 0, f = 1;char c = getchar();
	while(!isdigit(c)){if(c == '-') f = -1;c = getchar();}
	while(isdigit(c)) {y = y*10 + (c - '0'), c = getchar();}
	return y*f;
}
inline void read(int &x){x = Read();}
int y[N];
char x[N];
int Max() {
	int d = 0;
	Rep(i, n) d = max(d, y[i]);
	return d;
}
 
bool Check(int M) {
	int Ret = 0;
	int base = 1;
	Rep(i, n) {
		if(base * y[i] > m) return false;
		Ret += base * y[i];
		if(Ret > m) return false;
		if(i < n-1) {
			if(base > m/M) return false;
			base *= M;
		}
	}
	return Ret <= m;
}
 
void work() {
	scanf("%s", x);
	cin >> m;
	n = strlen(x);
	reverse(x, x+n);
	Rep(i, n) y[i] = x[i]-'0';
	if(n == 1) { 
		if(y[0] <= m) cout << 1 << endl;
		else cout << 0 << endl;
		return ;
	}
	int l = Max()+1, r = m, ans = 0;
	while(l <= r) {
		int M = (l+r) / 2;
		if(Check(M)) {
			l = M+1;
			ans = M-Max();
		} else {
			r = M-1;
		}
	} 
	cout << ans << endl;
}
 
signed main() {
  //freopen("1.in", "r", stdin);
  //freopen("1.out", "w", stdout);
  int T = 1;
 
  //cin >> T;
 
  while(T--) {
  	work();
  }
 
  return 0;
}
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl "\n"

int mul(int a,int b,int m){
	int cur=0;

	while(b>0){
		if(b&1)cur+=a;
		if(cur > m){
			return -1;
		}
		a*=2;
		b/=2;
		if(b>0 and a > m){
			return -1;
		}		
	}
	
	return cur;
}

bool solve(int base,string &x,int m){
	int num=0;
	int curPow=1;
	for(int i=0;i<x.size();i++){
		
		int temp = mul((x[i]-'0'),curPow,m);
		if(temp<0)return 0;
		
		num += temp;
		
		if(num > m){
			return 0;
		}
		temp=mul(curPow,base,m);
		
		if(temp<0 and i+1<x.size()){
			
			return 0;
		}
		
		curPow=temp;	
	}
	
	return 1;
}

signed main(){
//	ios_base::sync_with_stdio(0) , cin.tie(0);

	string x;
	int m;
	
	cin>>x;
	cin>>m;
	if(x.size()==1){
		if(x[0]-'0' > m){
			cout<<0<<endl;
		}else cout<<1<<endl;
		return 0;
	}
	int freq[10]{0};
	reverse(x.begin(),x.end());
	
	for(int i=0;i<x.size();i++){
		freq[x[i]-'0']++;
	}
	
	int maxy=0;
	for(int i=9;i>=0;i--){
		if(freq[i]>0){
			maxy=i;
			break;
		}
	}
	int l=maxy,r=1e18;
	r++;
	while(l+1<r){
		int mid=(l+r)/2;
		if(maxy != mid and solve(mid,x,m)){
			l=mid;	
		}else{
			r=mid;
		}
	}
	cout<<l-maxy<<endl;

	return 0;
}
