#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int MAXN = 60 + 5;

int n;
ll m;
char s[MAXN];

bool chk(ll base)
{ 
	ll cur = 0;
	for(int i=1; i<=n; ++i)
	{
		if(cur > m / base + 1) return 0;
		cur = cur * base + s[i] - '0';
		if(cur > m) return 0;
	}
	return cur <= m;
}

int main(void)
{
	scanf("%s%lld",s+1,&m);
	n = strlen(s+1);
	
	int mx = 0;
	for(int i=1; i<=n; ++i) mx = max(mx, s[i] - '0');
	
	if(n == 1) return printf("%d",s[1] - '0' <= m? 1: 0), 0;
	
	ll l = mx+1, r = 1e18;
	if(!chk(l)) return printf("0"), 0;
	while(l<r)
	{
		ll mid = (l+r+1)>>1;
		if(chk(mid)) l = mid;
		else r = mid-1;
	}
	
	printf("%lld",l - mx);
	return 0;
}
#include "bits/stdc++.h"

using namespace std;

typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<double, double> pdd;
typedef pair<ll, ll> pll;

#define endl "\n"
#define eb emplace_back
#define mem(a, b) memset(a , b , sizeof(a))

const ll INF = 0x3f3f3f3f;
// const ll mod = 998244353;
// const ll mod = 1e9 + 7;
const double eps = 1e-6;
const double PI = acos(-1);
const double R = 0.57721566490153286060651209;


void solve() {
    string s; ll M;
    cin >> s >> M;
    ll x = 0;
    for(int i = 0;i < (int)s.length(); i++) x = max(x, (ll)(s[i]- '0'));
    x++;
    if(s.length() == 1) {
        if(s[0] - '0' <= M) cout << 1 << endl;
        else cout << 0 << endl;
        return ;
    }
    ll l = 1, r = 1e18 + 10;
    ll t = 0;
    while(l <= r) {
        ll mid = (l + r) / 2;
        __int128 ans = 0;
        __int128 k = mid;
        bool flag = 1;
        for(int i = 0;i < (int)s.length(); i++) {
            ans = ans * k + (ll)(s[i] - '0');
            if(ans <= 0) { flag = 0; break; }
        }
        if(flag && ans <= M) {
            l = mid + 1;
            t = mid;
        }
        else r = mid - 1;
    }
    cout << max(0ll, t - x + 1) << endl;
}

signed main() {
    ios_base::sync_with_stdio(false);
    // cin.tie(nullptr);
    // cout.tie(nullptr);
#ifdef FZT_ACM_LOCAL
    freopen("../in.txt", "r", stdin);
    freopen("../out.txt", "w", stdout);
    signed test_index_for_debug = 1;
    char acm_local_for_debug = 0;
    do {
        if (acm_local_for_debug == '$') exit(0);
        if (test_index_for_debug > 20)
            throw runtime_error("Check the stdin!!!");
        auto start_clock_for_debug = clock();
        solve();
        auto end_clock_for_debug = clock();
        cout << "Test " << test_index_for_debug << " successful" << endl;
        cerr << "Test " << test_index_for_debug++ << " Run Time: "
             << double(end_clock_for_debug - start_clock_for_debug) / CLOCKS_PER_SEC << "s" << endl;
        cout << "--------------------------------------------------" << endl;
    } while (cin >> acm_local_for_debug && cin.putback(acm_local_for_debug));
#else
    solve();
#endif
    return 0;
}

