#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i = 0; i < (int)n; i++)
#define debug(x)      cerr << "L" << __LINE__ << ": " << #x << " = " << (x) << endl
#define debugvec(v)   rep(i, v.size()) cerr << "L" << __LINE__ << ": " << #v << "[" << i << "] = " << v[i] << endl;
#define debugvec2(v)  cerr << "L" << __LINE__ << ": " << #v << " = { "; rep(i, v.size()) cerr << v[i] << (i + 1 == v.size() ? "" : ", "); cerr << " }" << endl;
typedef long long ll;  /* 10^18 くらいまでいける */
typedef unsigned long long ull;  /* 10^18 くらいまでいける */

/* https://blog.hamayanhamayan.com/entry/2021/02/20/233715
 *
 *  M を n進数表記に変換して比較する
 */
string X;
ll M;
bool check(ll n) {
  vector<ll> Y;  // Mをn進数表記に変換
  ll m = M;
  while (0 < m){
	Y.push_back(m % n);
	m /= n;
  }
  reverse(Y.begin(), Y.end());

  // 例えばnが2進数や8進数の場合, 桁数が増えることがある.
  if (X.size() < Y.size())
	return true;

  // 例えばnが16進数の場合, 桁数が減ることがある.
  else if (X.size() > Y.size())
	return false;

  // 桁数が同じ時は大きい桁から1桁ずつ比較する
  for(ll i = 0; i < X.size(); i++){
	ll x = X[i] - '0';
	ll y = Y[i];

	if (x == y) continue;
	else if (x < y) return true;
	else return false;
  }

  // X == Y
  return true;
}

int main(){
  cin >> X;
  cin >> M;

  // もっとも大きい数字dを取得
  char d_char = '0';
  for (ll i = 0; i < X.length(); i++){
	d_char = X[i] > d_char ? X[i] : d_char;
  }
  ll d = d_char - '0';

  if (X.length() == 1){
	ll x = stoll(X);
	if (x <= M)
	  cout << "1" << endl;
	else
	  cout << "0" << endl;
	return 0;
  }

  // 2部探索
  ll min_v = d;
  ll max_v = 2e18;  // 問題の制約の最大値
  ll mid_v;

  // 2部探索はhighとlowの差が1になるまでwhileを回す
  while (min_v + 1 < max_v){
	mid_v = (min_v + max_v) / 2;
    // printf("min_v: %lld, mid_v: %lld, max_v: %lld\n", min_v, mid_v, max_v);
	if (check(mid_v)){
	  min_v = mid_v;
	}else{
	  max_v = mid_v;
	}
  }
  mid_v = (min_v + max_v) / 2;
  // printf("min_v: %lld, mid_v: %lld, max_v: %lld\n", min_v, mid_v, max_v);
  cout << mid_v - d << endl;
}

#include <bits/stdc++.h>

#define endl "\n"
#define int long long
#define debug(statement) \
    if (debugging)       \
    cerr << statement << endl
#define debug_variable(var) \
    if (debugging)          \
    cerr << (#var) << ": " << var << endl

const bool debugging = 1;

using namespace std;

template <class T>
ostream &operator<<(ostream &os, vector<T> V)
{
    for (auto v : V)
    {
        os << v << " ";
    }
    return os << "";
}

template <class T>
ostream &operator<<(ostream &os, set<T> S)
{
    for (auto s : S)
    {
        os << s << " ";
    }
    return os << "";
}

template <class L, class R>
ostream &operator<<(ostream &os, pair<L, R> P)
{
    return os << P.first << " " << P.second;
}

template <class L, class R>
ostream &operator<<(ostream &os, map<L, R> M)
{
    os << endl;
    for (auto m : M)
    {
        os << m << endl;
    }
    return os << "";
}

long long binaryExponentiation(long long base, long long power)
{
    //cout << base << " " << power << endl;
    long long result = 1;
    while (power > 0)
    {
        if (power & 1)
        {
            result = result * base;
        }
        base = base * base;
        power = power >> 1;
    }
    return result;
}

int32_t main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    string ex;
    cin >> ex;
    int N = ex.size();
    int M;
    cin >> M;
    int d = 0;
    for (int i = 0; i < N; i++)
    {
        d = max(d, (int)(ex[i] - '0'));
    }

    if (N == 1)
    {
        if (d + 1 > M && M != ((int)(ex[0] - '0')))
        {
            cout << 0 << endl;
        }
        else
        {
            cout << 1 << endl;
        }
        return 0;
    }

    if (d + 1 >= M)
    {
        cout << 0 << endl;
        return 0;
    }

    int l = d + 1;
    int r = M;
    int ans = 0;
    while (l <= r)
    {
        bool overflow = 0;
        int mid = (r - l) / 2 + l;
        //cout << mid << endl;
        int res = binaryExponentiation(mid, N - 1);
        if (log10(mid) * (N - 1) > 18)
        {
            r = mid - 1;
            continue;
        }

        int total = 0;
        for (int i = 0; i < N; i++)
        {
            if ((res * ((int)(ex[i] - '0'))) / res != ((int)(ex[i] - '0')) || (total + ((int)(ex[i] - '0')) * ex[i]) - ((int)(ex[i] - '0')) * ex[i] != total)
            {
                overflow = 1;
                break;
            }
            total += (res * ((int)(ex[i] - '0')));
            res /= mid;
        }

        if (total <= M && !overflow)
        {
            //cout << "WOOSYFACE" << endl;
            ans = mid;
            l = mid + 1;
        }
        else
        {
            r = mid - 1;
        }
    }
    if (ans == 0)
    {
        cout << 0 << endl;
    }
    else
    {
        cout << ans - d << endl;  
    }
    
    //cout << l << endl;
    //cout << r << endl;
    return 0;
}