#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
using ll = long long;
using P = pair<int, int>;

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

    if (x.size() == 1){
        if(stoi(x) <= m) cout << 1 << endl;
        else cout << 0 << endl;
        return 0;
    }

    ll d = 0;
    for(char c: x) d = max(d, ll(c - '0'));

    ll ac = d;
    ll wa = m + 1;

    while(wa - ac > 1){
        ll wj = (wa + ac) / 2;
        ll v = 0;
        for(char c: x){
            if (m/wj < v){
                v = m + 1;
                break;
            }
            else v = v * wj + ll(c - '0');
        }
        if (v <= m) ac = wj;
        else wa = wj; 
    }
    cout << ac - d << endl;
    return 0;
}
#include <bits/stdc++.h>

using namespace std;

template <typename T>
bool chmax(T& a, const T b) {
  if (a < b) {
    a = b;
    return true;
  } else {
    return false;
  }
}

template <typename T>
bool chmin(T& a, const T b) {
  if (a > b) {
    a = b;
    return true;
  } else {
    return false;
  }
}

void solve(std::vector<int64_t> X, int64_t M) {
  int64_t d = *max_element(X.begin(), X.end());
  int L = X.size();

  auto convert_base = [](int64_t K, int64_t base) -> vector<int64_t> {
    vector<int64_t> digits;
    while (K) {
      digits.push_back(K % base);
      K /= base;
    }
    reverse(digits.begin(), digits.end());
    return digits;
  };

  auto calc = [&](int64_t K, int64_t base) -> bool {
    vector<int64_t> Y = convert_base(K, base);
    if (X.size() < Y.size()) {
      return true;
    } else if (X.size() > Y.size()) {
      return false;
    }

    for (int i = 0; i < X.size(); i++) {
      if (X[i] < Y[i]) {
        return true;
      } else if (X[i] > Y[i]) {
        return false;
      }
    }
    return true;
  };

  if (L == 1) {
    if (calc(M, d + 1)) {
      cout << 1 << endl;
    } else {
      cout << 0 << endl;
    }
    return;
  }

  if (!calc(M, d + 1)) {
    cout << 0 << endl;
    return;
  }

  int64_t ok = d + 1;
  int64_t ng = M + 1;
  while (ok + 1 < ng) {
    int64_t base = (ok + ng) / 2;
    if (calc(M, base)) {
      ok = base;
    } else {
      ng = base;
    }
  }
  cout << ok - d << endl;
}

int main() {
  std::string X;
  std::cin >> X;
  vector<int64_t> x;
  for (char c : X) {
    x.push_back(c - '0');
  }
  int64_t M;
  scanf("%ld", &M);
  solve(x, M);
  return 0;
}
