#include <bits/stdc++.h>

using namespace std;

bool can_evaluate(string &X, long long B, long long M){
  long long val = 0;

  for(int i = 0; i < X.size(); i++){
    int x = X[i] - '0';
    if(val > (M-x)/B) return false;
    val = val*B + x;
  }

  return val <= M;
}

int main(){
  string X; long long M;
  while(cin >> X >> M){
    if(X.size() == 1){
      printf("%d\n", stod(X) <= M ? 1 : 0);
      continue;
    }

    int min_b = 0;
    for(char ch : X){
      min_b = max(min_b, ch-'0'+1);
    }

    if(!can_evaluate(X, min_b, M)){
      printf("0\n");
      continue;
    }

    long long max_b = min_b;
    while(can_evaluate(X, max_b, M)) max_b <<= 1;

    long long lo = min_b, up = max_b, B = min_b;

    while(lo <= up){
      long long mid = (lo + up) >> 1;

      if(can_evaluate(X, mid, M)){
	lo = mid+1;
	B = mid;
      } else {
	up = mid-1;
      }
    }

    printf("%lld\n", B - min_b + 1);
  }
}

#include<bits/stdc++.h> 
using namespace std;
typedef long long ll;
#define all(x) (x).begin(),(x).end()
template<typename T1,typename T2> bool chmin(T1 &a,T2 b){if(a<=b)return 0; a=b; return 1;}
template<typename T1,typename T2> bool chmax(T1 &a,T2 b){if(a>=b)return 0; a=b; return 1;}
int dx[4]={0,1,0,-1}, dy[4]={1,0,-1,0};
long double eps = 1e-9;
long double pi = acos(-1);

using lll = __int128_t;

signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout << fixed << setprecision(20);

	string s;
	cin>>s;
	ll n;
	cin>>n;
	ll ma = 0;
	for(ll i=0;i<(int)s.size();i++)chmax(ma,s[i]-'0');
	if(s.size() == 1){
		// assert(ma>n);
		if(ma > n)cout << 0 << endl;
		else cout << 1 << endl;
		return 0;
	}
	int x = s.size();
	lll low=0,up=1000000000000000009,mid;
	while(up-low>1){
		mid=(up+low)/2;
		lll m = n;
		bool pos = 1;
		for(int i=1;i<x;i++)m/=mid;
		if(m == 0)pos=false;
		if(pos){
			lll now = 0;
			for(int i=0;i<x;i++){
				now *= mid;
				now += s[i]-'0';
			}
			if(now > n)pos=false;
		}
		if(pos){
			low=mid;
		}
		else{
			up=mid;
		}
	}
	chmin(low,n);
  ll ans = low - ma;
  chmax(ans,0);
        cout << ans << endl;

}