#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

int main(){
  string x;
  ll m;
  cin >> x >> m;
  ll d = 0, lm = 9223372036854775807;
  for(char pp : x){ d = max(d, (ll)(pp - '0') ); }
  if(x.size() == 1){ 
    if((ll)(x[0] - '0') <= m) {cout << 1; return 0;}
  	else {cout << 0; return 0;}
  }
  ll mind = d, maxd = m;
  while(mind < maxd){
    ll nu = (mind + maxd)/2, tm = 0;
    int f=0;
    for(char xi : x){
      if(tm >= (lm-10)/nu){ f = 1; break;}
      tm *= nu;
      tm += (ll)(xi - '0');
    }
    if(f == 1 || tm > m) maxd = nu - 1;
    else mind = nu + 1;
  }
  ll ddd = 0, dnu = mind, f = 0;
  for(char xi : x){
      if(ddd >= (lm-10)/dnu){ f = 1; break;}
      ddd *= dnu;
      ddd += (ll)(xi - '0');
    }
  maxd = mind;
  if(f == 0 && ddd <= m) {if(maxd < d) {cout << 0;} else {cout <<  maxd - d;} }
  else { if(maxd >= d+1) {cout << maxd - d - 1;} else { cout << 0; } }
  return 0;
}
# include <cstdio>
# include <cstring>

namespace Main {
    namespace Source {
        typedef short unsigned int hu;
        typedef long long unsigned int llu;
        static inline const hu max(const hu a, const hu b) { return a < b ? b : a; }
        static inline const void amax(hu& a, const hu b) { a = max(a, b); }
    }
    using namespace Source;
    enum { X = 60 };
    static char x[X + 1];
    static hu log, mx;
    static llu m;
    static inline const bool check(const llu k) {
        llu r(0), b(1);
        for (hu i(1); i <= log; ++i, b *= k) {
            if ((m - r) / b < (const llu)(x[log - i] - '0')) return false;
            r += b * (x[log - i] - '0');
            if (i < log and m / b < k) return false;
        }
        return true;
    }
    static inline const void main() {
        scanf("%s%llu", x, &m), log = strlen(x);
        for (hu i(0); i < log; ++i) amax(mx, x[i] - '0');
        if (mx > m) return (const void)puts("0");
        if (log == 1) return (const void)puts("1");
        llu l(mx), r(m + 1);
        while (r - l > 1) (check((l + r) / 2) ? l : r) = (l + r) / 2;
        printf("%llu\n", l - mx);
    }
}

signed int main() { Main::main(); return 0; }