#include <bits/stdc++.h>
#define ll long long int
using namespace std;
ll power(ll x, ll n, ll m) {
	if (n == 0ll)
		return 0ll;
	ll y = power(x, n / 2ll, m);
	if ((y == -1ll) || (y > m - y))
		return -1ll;
	y = (y + y);
	if (n % 2ll) {
		if ((x > m) || (y > m - x)) {
			return -1ll;
		}
		y = y + x;
	}
	return y;
}
bool f(string x, ll b, ll n, ll m) {
	ll y = 0ll, p = 1ll, z;
	for (ll i = n - 1; i >= 0; i--) {
		z = power(1ll * (x[i] - '0'), p, m);
		if ((z == -1ll) || (y > m - z)) {
			return false;
		}
		y = z + y;
		p = power(p, b, m);
		if (i) {
			if (p == -1ll) {
				return false;
			}
		}
	}
	return true;
}
string strip(string s) {
	int n = s.length(), i;
	for (i = 0; i < n; i++) {
		if (s[i] != '0') {
			break;
		}
	}
	return s.substr(i);
}
int main() {
#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
#endif

	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cout.precision(10);
	string x;
	ll m, d, n, l, u, mid;
	cin >> x >> m;
	x = strip(x);
	n = x.length();
	d = (x[0] - '0');
	for (int i = 1; i < n; i++) {
		d = max(d, 1ll * (x[i] - '0'));
	}
	if (n == 1) {
		cout << ((d <= m) ? 1ll : 0ll) << endl;
		return 0;
	}
	l = d + 1ll, u = 1e18L;
	while (l < u) {
		mid = l + (1ll + u - l) / 2ll;
		if (f(x, mid, n, m))
			l = mid;
		else
			u = mid - 1ll;
	}
	if (f(x, l, n, m)) {
		cout << max(0ll, l - d) << endl;
	} else {
		cout << 0ll << endl;
	}
	return 0;
}
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef long double db;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
template <typename T>
using ordered_multiset = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;
template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
#define pll pair<ll,ll>
#define pb push_back
#define eb emplace_back
#define ub(v,val) upper_bound(v.begin(),v.end(),val)
#define np(str) next_permutation(str.begin(),str.end())
#define lb(v,val) lower_bound(v.begin(),v.end(),val)
#define sortv(vec) sort(vec.begin(),vec.end())
#define rev(p) reverse(p.begin(),p.end());
#define v vector
#define repc(i,s,e) for(ll i=s;i<e;i++)
#define fi first
#define se second
#define mset(a,val) memset(a,val,sizeof(a));
#define repr(i,n) for(i=n-1;i>=0;i--)
#define rep(i,n) for(i=0;i<n;i++)
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define at(s,pos) *(s.find_by_order(pos))
#define set_ind(s,val) s.order_of_key(val)
long long int M = 1e9 + 7 ;
long long int inf = 9 * 1e18;
const double PI = acos(-1);
//CLOCK
ll begtime = clock();
#define time() cout << "\n\nTime elapsed: " << (clock() - begtime)*1000/CLOCKS_PER_SEC << " ms\n\n";
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
//CLOCK ENDED
ll n, m;
// modular exponentiation
ll binpow(ll val, ll deg)
{
	if (deg < 0)
		return 0;
	if (!deg)
		return 1 % M;
	if (deg & 1)
		return binpow(val, deg - 1) * val % M;
	ll res = binpow(val, deg >> 1);
	return (res * res) % M;
}
ll power(ll val, ll deg)
{
	if (deg < 0)
		return 0;
	if (!deg)
		return 1;
	if (deg & 1)
		return power(val, deg - 1) * val;
	ll res = power(val, deg >> 1);
	return (res * res);
}

int main() {
	// your code goes here
	IOS;
#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
#endif

	ll i, j, t, k, x;

	string s;
	cin >> s;
	ll highest = 0;
	for (auto u : s) {
		highest = max(highest, (ll)(u - '0'));
	}
	rev(s);
	cin >> M;
	ll check = M;
	if (s.size() == 1) {
		x = s[0] - '0';
		if (x <= M) cout << 1;
		else cout << 0;
		return 0;
	}

	ll l = highest + 1, r = 1e18, mid;
	ll ans = highest;


	while (l <= r) {
		mid = (l + r) / 2;
		bool flg = 0;
		rep(i, s.size()) {
			double jam = pow(mid, i);
			if (jam > 1e18) flg = 1;
			else {
				ll jam = power(mid, i);
				if (jam > check)flg = 1;
			}
		}
		ll num = 0;
		rep(i, s.size()) {
			num += power(mid, i) * ll(s[i] - '0');
			if (num > check) flg = 1;
		}
		if (flg) {
			r = mid - 1;
		}
		else {
			ans = mid;
			l = mid + 1;
		}

	}
	cout << ans - highest;

	return 0;


}