#include "bits/stdc++.h"

using namespace std;

typedef long long ll;

const ll INFLL = 2e18 + 5;

ll good(string x, ll n){
	ll ans = 0;
	for(char c: x){
		if(ans > INFLL / n)	return INFLL;
		ans *= n;
		ans += int(c - '0');
	}
	return ans;
}

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int t = 1;	//cin >> t;
	for(int tt = 0; tt < t; tt++){
		string x;	cin >> x;
		ll m;	cin >> m;
		int d = 0, n = (int) x.size();
		for(int i = 0; i < n; i++){
			d = max(d, x[i] - '0');
		}
		if((int) x.size() == 1){
			ll xd = (x[0] - '0');
			if(xd <= m)	cout << "1\n";
			else cout << "0\n";
		}else{
			ll lo = d, hi = m + 1;
			while(hi - lo > 1){
				ll mid = (lo + hi) / 2;
				if(good(x, mid) <= m){
					lo = mid;
				}else{
					hi = mid;
				}
			}
			cout << lo - d << "\n";
		}
	}
}

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pll = pair<long long, long long>;
constexpr char ln =  '\n';
constexpr long long MOD = 1000000007;
constexpr long long INF = 1000000000 + 100;
constexpr long long LINF = 1000000000000000000 + 100;
#define all(v) v.begin(), v.end()
#define rep(i, n) for(int i=0;i<(n);i++)
#define rept(i, j, n) for(int i=(j); i<(n); i++)
#define rrep(i, n) for(int i=(n); i>=0; i--)
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }



int main(){
    string X; ll M; cin >> X >> M;

    if(X.size()==1){
        if(M < (X[0]-'0'))cout << 0 << ln;
        else cout << 1 << ln;
        return 0;
    }

    int mx_x = -1;
    //xに含まれる最大の値
    for(auto x:X){
        chmax(mx_x, x-'0');
    }

    reverse(all(X));
    auto check = [&](ll val) -> bool{
        ll num = 0, tmp = 1;
        rep(i, X.size()){
            num += tmp * (X[i]-'0');
            //オーバーフロー検知
            if(i != (int)X.size()-1 and tmp > (LONG_LONG_MAX/9) /val)return false;
            tmp *= val;
        }
        if(num <= M)return true;
        return false;
    };

    //Xを基数変換してM以下になるかどうか
    ll ok = mx_x, ng = LINF;
    while(ng - ok > 1){
        ll mid = (ok + ng) / 2;
        if(check(mid))ok = mid;
        else ng = mid;
    }
    cout << ok - mx_x << ln;
}
