#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<sstream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<climits>
#include<cmath>
#include<string>
#include<vector>
#include<set>
#include<map>
#include<queue>
#include<numeric>
#include<functional>
#include<algorithm>
#include<bitset>
#include<tuple>
#include<unordered_set>
#include<unordered_map>
#include<random>
#include<array>
#include<cassert>
using namespace std;
#define INF ((1<<30)-1)
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define all(v) v.begin(),v.end()




int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	string x;
	long long m;

	cin >> x >> m;
	long long d = 0;
	for (char c : x) d = max<long long>(d, c - '0');

	if (x.size() == 1) {
		if (x[0] - '0' <= m)cout << 1 << endl;
		else cout << 0 << endl;
		return 0;
	}
	

	long long lb = d, ub = m + 1;

	while (ub - lb > 1) {
		long long mid = (lb + ub) / 2;
		long long v = 0;
		for (char c : x) {
			if (v > (m + mid - 1) / mid) {
				v = -1;
				break;
			}
			v *= mid;
			v += c - '0';
		}
		if (v > m) {
			v = -1;
		}
		if (v == -1) ub = mid;
		else lb = mid;
	}
	cout << lb - d << endl;


	return 0;
}

#include <bits/stdc++.h>
#include <string>

#define rep(i,n) for(int i=0;i < (n);i++)
#define rep2(i, s, n) for (int i = (s); i < (n); i++)
#define rrep(i,n) for(int i=n-1;i>=0;i--)
#define fi first
#define se second
#define pb push_back
#define ALL(a) (a).begin(),(a).end()

typedef long long ll;
typedef unsigned long long ull;

const ll MOD=1000000007ll;
const int MAX=5100000;

using namespace std;

// aよりもbが大きいならばaをbで更新する
// (更新されたならばtrueを返す)
template <typename T>
bool chmax(T &a, const T& b) {
  if (a < b) {
    a = b;  // aをbで更新
    return true;
  }
  return false;
}
// aよりもbが小さいならばaをbで更新する
// (更新されたならばtrueを返す)
template <typename T>
bool chmin(T &a, const T& b) {
  if (a > b) {
    a = b;  // aをbで更新
    return true;
  }
  return false;
}

ll fact[MAX], fact_inv[MAX];

ll power(ll a, ll b){
	ll res=1;
	while(b>0){
		if(b&1) res=res*a%MOD;
		a=a*a%MOD;
		b>>=1;
	}
	return res;
}

// nCr
ll comb(ll n, ll r){
	ll t=1000000;
	fact[0]=1;
	    for(int i=0;i<t;i++){ fact[i+1]=fact[i]*(i+1)%MOD;}
	fact_inv[t]=power(fact[t], MOD-2);
	for(int i=0;i<t;i++){ fact_inv[i]=fact_inv[i+1]*(i+1)%MOD;}
	return (fact[n]*fact_inv[r])%MOD*fact_inv[n-r]%MOD;
}


const int N=100;
char x[N];
long long int m,sans,len;
bool check(long long int i){
	long long int ans=0;
	for(int o=0;o<=len-1;o++){
		if(ans>m*1.0/i){break;}
		ans=ans*i+x[o]-'0';
		if(ans>m){break;}
		else if(o==len-1)return 1;
	}
	return 0;
}
int main(){
	cin>>x;
	len=strlen(x);
	scanf("%lld",&m);
	if(len==1){
		if(x[0]-'0'<=m)
		printf("1\n");
		else 
		printf("0\n");
		
		return 0;
	}
	int maxn=1;
	for(int i=len-1;i>=0;i--){
		maxn=max(maxn,x[i]-'0'+1);
	}
	long long int l=maxn,r=m,mid,best=maxn-1;
	while(l<=r){
		mid=(l+r)>>1;
		if(check(mid)){
			best=mid;
			l=mid+1;
		}
		else{
			r=mid-1;
		}
	}
	while(check(best+1))best=best+1;
	printf("%lld\n",best-maxn+1);
	return 0;
}
