#include<bits/stdc++.h>
#include<bits/extc++.h>
#pragma GCC optimize("Ofast")
using namespace std;
using namespace __gnu_pbds;
template<typename TH> void _dbg(const char* sdbg, TH h) { cerr<<sdbg<<"="<<h<<"\n"; }
template<typename TH, typename... TA> void _dbg(const char* sdbg, TH h, TA... t){
	while(*sdbg != ',') { cerr<<*sdbg++; } cerr<<"="<<h<<","; _dbg(sdbg+1, t...);
}
#ifdef DEBUG
#define debug(...) _dbg(#__VA_ARGS__, __VA_ARGS__)
#define debugv(x) {{cerr<<#x<<": "; for(auto i:x) cerr<<i<<" "; cerr<<endl;}}
#define debugr(l,r,x) {{cerr<<#x<<": "; for(int i=l;i<=r;i++) cerr<<x<<" "; cerr<<endl;}}
#else
#define debug(...) (__VA_ARGS__)
#define debugv(x)
#define debugr(l,r,x)
#define cerr while(0) cerr
#endif
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> pii;
#define priority_queue std::priority_queue
#define F first
#define S second
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;

ll INF=1e18;
ll val(string x, ll M){
	ll ans=0;
	for(char c:x){
		int d=c-'0';
		if(ans > INF/M) return INF+1;
		ans=ans*M+d; 
	}
	return ans;
}
signed main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	string x;
	ll m;
	cin>>x>>m;
	if(x.size()==1){
		if((int) x[0]-'0'<=m) cout<<1;
		else cout<<0;
		return 0;
	}
	int d=0;
	for(char c:x){
		d=max(d, (int) c-'0');
	}
	ll L=d, R=m;
	while(L<R){
		ll M=(L+R+1)/2;
		if(val(x, M)<=m) L=M;
		else R=M-1;
	}
	cout<<L-d;
}
#include <bits/stdc++.h>
#define int long long
#define double long double
using namespace std;
const int MOD = 1000000007;
const int INF = 1000000000000000000;
using Graph = vector<vector<int>>;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)

signed main(){
  string S;
  cin >> S;
  int M;
  cin >> M;

  if( S == "1" ){
    cout << 1 << endl;
    return 0;
  }else if( S.size() == 1 ){
    if( (int)S[0]-'0' <= M ) cout << 1 << endl;
    else cout << 0 << endl;
    return 0;
  }

  reverse(S.begin(), S.end());

  int maxnum = 0;
  rep(i, S.size()) maxnum = max(maxnum, (int)(S[i]-'0'));

  int l = 0;
  int r = M+1;
  while( r-l > 1 ){
    int mid = (l+r)/2;
    bool overf = 0; //今見てる数が10^18を超えているか
    bool check = 1;
    int kake = 1;
    int now = 0;
    rep(i, S.size()){
      int c = S[i]-'0';
      if( overf == 1 ){ //今見てる数がオーバーフローする場合
        if( c > 0 ){
          check = 0;
          break;
        }else continue;
      }else now += c*kake;

      if( kake > M/mid ) overf = 1;
      if( overf == 0 ) kake *= mid;
    }
    if( check == 1 && now <= M ) l = mid;
    else r = mid;
  }

  if( r > maxnum ) cout << r-maxnum-1 << endl;
  else cout << 0 << endl;
}
