#define NDEBUG

#include <bits/stdc++.h>

using namespace std;

void dbg() {
    cerr << endl;
}

template <typename U, typename... Ts>
void dbg(U foo, Ts... bar) {
    cerr << ' ' << to_string(foo);
    dbg(bar...);
}

#ifndef NDEBUG
#define debug(...) cerr << '[' << #__VA_ARGS__ << "]: ", dbg(__VA_ARGS__)
#else
#define debug(...) ((void)0)
#endif

int greatestDigit(const string &x) {
    int res = 0;
    for (const auto &z : x) {
        res = max(res, z - '0');
    }
    return res;
}

long long baseN(const string &x, long long n) {
    long long res = 0;
    for (const auto &z : x) {
        if (res > (long double)(LLONG_MAX)/n) {
            return LLONG_MAX;
        }
        res = res * n;
        if (res > LLONG_MAX - (z - '0')) {
            return LLONG_MAX;
        }
        res += z - '0';
    }
    return res;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    string x;
    long long m;
    cin >> x >> m;
    if (x.length() == 1) {
        cout << (x[0] - '0' <= m) << '\n';
        return 0;
    }
    int d = greatestDigit(x);
    long long l = d + 1, r = m, mid = r / 2 + l / 2, res = -1;
    debug(l, r, mid);
    while (l <= r) {
        debug(l, r, mid, baseN(x, mid));
        if (baseN(x, mid) <= m) {
            res = mid;
            l = mid + 1;
        } else {
            r = mid - 1;
        }
        mid = r / 2 + l / 2;
        if (r % 2 == 1 && l % 2 == 1) {
            mid++;
        }
    }
    if (res == -1) {
        cout << 0 << '\n';
        return 0;
    }
    debug(res, d);
    cout << res - d << '\n';
    return 0;
}
#include <bits/stdc++.h>
#include <math.h>
using namespace std;
using ll = long long;
using vll = vector<ll>;
using vvll = vector<vll>;
using vpl = vector<pair<ll, ll>>;
using pll = pair<ll, ll>;
#define rep(i, k, n) for(ll i = k; i < n; i++)
#define pb push_back
#define mp make_pair

ll change(string x, ll k, ll m){
    ll rec = 0;
    rep(i, 0, x.size()){
        if((x[i] - '0')*pow(k, x.size()-1-i) > m) return -1;
        rec += (x[i] - '0')*pow(k, x.size()-1-i);
        if(rec > m) return -1;
    }
    return rec;
}

int main(){
    string x; cin >> x;
    ll m; cin >> m;

    if(x.size() == 1){
        if(x[0] - '0' <= m) cout << 1 << endl;
        else cout << 0 << endl;
    }
    else{
        ll d = 0;
        rep(i, 0, x.size()){
            if(x[i] - '0' > d) d = x[i] - '0';
        }

        ll left = 0;
        ll right = m+1;

        while(right - left > 1){
            ll mid = (right + left) / 2;
            ll p = change(x, mid, m);

            if(p == -1 || p > m) right = mid;
            else left = mid; 
        }

        cout << max(left - d, 0LL) << endl;
    }
}