#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")

#include <algorithm>
#include <bitset>
#include <climits>
#include <cmath>
#include <cstring>
#include <deque>
#include <forward_list>
#include <functional>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <queue>
#include <set>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>

using namespace std;
typedef long long ll;
typedef pair<int, int> P;
typedef bitset<16> BS;
struct edge {
    int to, cost, id;
};
const double EPS = 1E-09;
const ll MOD = 1E+09 + 7; // =998244353;
const ll INF = 1E18;
const int MAX_N = 1E+05;

ll dx[4] = { -1, 1, 0, 0 }, dy[4] = { 0, 0, -1, 1 };

ll M;

string X;

bool f(ll n);

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> X >> M;

    ll d = 0;
    for (auto x : X) {
        d = max(d, (ll)(x - '0'));
    }

    //reverse(X.begin(), X.end());

    ll high = M + 1, low = 0;
    ll ans = 0;
    //ll high = (ll)(pow((double)M / (double)(X[X.size() - 1]), 1.0 / ((double)X.size() - 1.0))) + 100
    if (X.size() > 1) {
        while (true) {
            ll mid = (high + low) / 2;
            if (mid == high || mid == low)
                break;
            if (f(mid)) {
                high = mid;
            } else {
                low = mid;
            }
            //cout << "high = " << high << ", low = " << low << "\n";
        }
    } else {
        if (X[0] - '0' <= M)
            ans = 1;
    }

    /*
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            cout << "i = " << i << ", j = " << j << ", dp = " << dp[i][j] << "\n";
        }
    }
    */

    cout << (X.size() == 1 ? ans : max(0LL, low - d)) << "\n";

    return 0;
}

bool f(ll n)
{
    ll res = 0;
    for (auto c : X) {
        ll x = c - '0';
        if (res > M / n)
            return true;
        res = res * n + x;
    }
    //cout << "n = " << n << ", res = " << res << "\n";
    return res > M;
}

// bool f(ll n)
// {
//     vector<ll> res;
//     ll m = M;
//     while (m > 0) {
//         res.push_back(m % n);
//         m /= n;
//     }
//     // cout << "n = " << n << "\n";
//     // cout << "Xsize = " << X.size() << ", res.size = " << res.size() << "\n";
//     if (res.size() != X.size())
//         return X.size() > res.size();

//     reverse(res.begin(), res.end());
//     for (int i = 0; i < X.size(); i++) {
//         ll x = X[i] - '0';
//         if (x > res[i])
//             return true;
//         else if (x < res[i])
//             return false;
//     }
//     return false;
// }
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <utility>
#include <set>
#include <map>
#include <cmath>
#include <queue>
#include <cstdio>
#include <limits>
#define rep(i,n) for(int i = 0; i < n; ++i)
#define rep1(i,n) for(int i = 1; i <= n; ++i)
using namespace std;
template<class T>bool chmax(T &a, const T &b) { if(a < b){ a = b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if(a > b){ a = b; return 1; } return 0; }
template<class T> inline int  sz(T &a) { return a.size(); }
using ll = long long; using ld = long double;
using pi = pair<int,int>; using pl = pair<ll,ll>;
using vi = vector<int>; using vvi = vector<vi>;
using vl = vector<ll>; using vvl = vector<vl>;
const int inf = numeric_limits<int>::max();
const ll infll = numeric_limits<ll>::max();
int main()
{
  string s; cin >> s;
  ll m; cin >> m;
  int n = sz(s);
  ll mx = 0;
  rep(i,n) {
    ll tmp = s[i] - '0';
    chmax(mx, tmp);
  }
  if(n == 1) {
    if(mx <= m) cout << 1 << "\n";
    else cout << 0 << "\n";
    return 0;
  }
  ll lb = mx, ub = 1000000000000000001;
    ll an = s[0] - '0';
  while(ub - lb > 1) {
    ll B = (ub + lb) / 2;
//    cout << B << "\n";
    ll x = an;
    int cnt = 0;
    while(x <= m/B) {
      x *= B;
//      cout << x << "\n";
      cnt++;
      if(cnt == n-1) break;
    }

    if(cnt==n-1) {
      ll sum = 0;
      ll buf = 1;
      for(int j = n-1; j >= 1; --j) {
        ll tmp = s[j] - '0';
        sum += tmp * buf;
        buf *= B;
      }
      if(an*buf <= m - sum) {
        lb = B;
      }
      else ub = B;
    }
    else ub = B;
  }
  cout << lb-mx << "\n";


  return 0;
}
