#include <bits/stdc++.h>
typedef long long ll;
typedef long double ld;
#define fr(i, a, b) for (ll i = a; i < b; i++)
#define rf(i, a, b) for (ll i = a; i >= b; i--)
typedef std::vector<long long> vi;
#define F first
#define S second
#define fast                      \
    ios_base::sync_with_stdio(0); \
    cin.tie(0);                   \
    cout.tie(0);
#define mod 1000000007
#define PB push_back
#define MP make_pair
#define PI 3.14159265358979323846
#define all(a) a.begin(), a.end()
#define mx(a) *max_element(all(a))
#define mn(a) *min_element(all(a))
const ll INF = LLONG_MAX / 2;
const ll N = 2e5 + 1;
using namespace std;
ll n, maxid = 0, m;
ll pow1(ll n, ll p)
{
    if (p == 0)
        return 1;
    ll x = pow1(n, p / 2);
    if (x > m || x >= 1000000001)
        return INF;
    x = (x * x);
    if (x > m)
        return INF;
    if (p % 2 == 0)
        return x;
    else
    {
        if (x * n > m)
            return INF;
        return (x * n);
    }
}
string x;
bool check(ll k)
{
    ll j = 0, ans = 0;
    rf(i, n - 1, 0)
    {
        if (pow1(k, j) == INF)
            return false;
        if (pow1(k, j) + ans > m || ans > m)
            return false;
        ans += (pow1(k, j) * ((ll)(x[i] - '0')));
        j++;
    }
    if (ans > m)
        return false;
    return true;
}
int main()
{
    fast;
    ll t = 1;
    // std::cin >> t;
    while (t--)
    {
        cin >> x;
        n = x.length();
        cin >> m;
        if (x.length() == 1)
        {
            ll c = x[0] - '0';
            if (m < c)
                cout << 0 << "\n";
            else
                cout << 1 << "\n";
            continue;
        }
        fr(i, 0, n)
            maxid = max(maxid, (ll)(x[i] - '0'));
        ll l = maxid + 1, r = m + 1;
        // cout << l << "\n";
        // cout << maxid << "\n";
        while (l <= r)
        {
            ll mid = (l + r) / 2;
            if (check(mid))
            {
                l = mid + 1;
            }
            else
            {
                r = mid - 1;
            }
        }
        cout << l - 1 - maxid << "\n";
    }
}

#include <bits/stdc++.h>
using namespace std;

typedef unsigned long long ull;
typedef __int128 ll;
string x;
ull m;

bool check(ull mid)
{
	ll ans=0;
	int flag=1;
	for(int i=0;i<x.size();i++)
	{
		ans=ans*mid+ll(x[i]-'0');
		if(ans>m)
		{
			flag=0;
			break;
		}
	}
	return flag;
}

int main()
{
	char c='0';
	cin>>x>>m;
	for(int i=0;i<x.size();i++)
	{
		c=max(c,x[i]);
	}
	ull t=c-'0';
	if(x.size()==1)
	{
		if(t<=m) cout<<1<<endl;
		else cout<<0<<endl;
	}
	else
	{
		ull l=0,r=1e18;
		while(l<r)
		{
			ull mid=(l+r+1)>>1;
			if(check(mid)) l=mid;
			else r=mid-1;
		}
		if(l<t) cout<<0<<endl;
		else cout<<l-t<<endl;
	}
	
	return 0;
}