// Problem: D - Base n
// Contest: AtCoder - AtCoder Beginner Contest 192
// URL: https://atcoder.jp/contests/abc192/tasks/abc192_d
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
// Powered by CP Editor (https://github.com/cpeditor/cpeditor)

// Disclaimer: Don't copy my template, it may lead to plagiarism.
/* Author: Soumy Jain
   Handle: soumy_jain || soumyjain
   "Beautiful flowers too, eventually wither and fall. That's the fate of all living beings."
   "I hate perfection. To be perfect is to be unable to improve any furthur." - Mayuri Kurotsuchi | Bleach
   "I smile to show the pressure of heroes and to trick the fear inside of me."
   "Gravel may be gravel, but me? I'm the gravel that shatters diamonds."
   "If you were to write a story with me in the lead role, it would certainly be...a TRAGEDY." - Kaneki Ken | Tokyo
   Ghoul
*/
/******************************************************************************/
// clang-format off
#include <bits/stdc++.h>
#define ll        long long
#define ull       unsigned long long
#define SPEEDHACK ios_base::sync_with_stdio(false);cin.tie(NULL);
#define Tc        ll tc; cin>>tc; while(tc--)
#define Qu        ll qu; cin>>qu; while(qu--)
#define ff        first
#define ss        second
#define sz(v)     (ll)(v).size()
#define file      freopen("input.txt","r",stdin);freopen("output.txt","w",stdout);
#define MOD       1000000007      // 998244353
using namespace std;
/******************************************************************************/
void __print(int x) { cerr << x; }
void __print(long x) { cerr << x; }
void __print(ll x) { cerr << x; }
void __print(unsigned x) { cerr << x; }
void __print(unsigned long x) { cerr << x; }
void __print(ull x) { cerr << x; }
void __print(float x) { cerr << x; }
void __print(double x) { cerr << x; }
void __print(long double x) { cerr << x; }
void __print(char x) { cerr << '\'' << x << '\''; }
void __print(const char *x) { cerr << '\"' << x << '\"'; }
void __print(const string &x) { cerr << '\"' << x << '\"'; }
void __print(bool x) { cerr << (x ? "true" : "false"); }

template<typename T, typename V>
void __print(const pair<T, V> &x) { cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}'; }
template<typename T>
void __print(const T &x) { int f = 0; cerr << '{'; for (auto &i : x) cerr << (f++ ? "," : ""), __print(i); cerr << "}"; }
void _print() { cerr << "]\n"; }
template <typename T, typename... V>
void _print(T t, V... v) { __print(t); if (sizeof...(v)) cerr << ", "; _print(v...); }
#ifndef ONLINE_JUDGE
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define debug(x...)
#endif
// clang-format on

/***********************************MAIN***************************************/
// Are you ready to face the wrath of test cases? Good luck noob Soumy!

int main()
{
    SPEEDHACK
    // file
    string s;
    cin >> s;
    ll m;
    cin >> m;
    ll d = 0;
    for (ll i = 0; i < sz(s); i++)
    {
        d = max(d, (ll)s[i] - 48);
    }
    if (sz(s) == 1)
    {
        if (s[0] - 48 > m)
            cout << 0;
        else
            cout << 1;
        return 0;
    }
    ll c = 0;
    if (sz(s) == 2 || sz(s) == 3 || sz(s) == 4)
    {
        for (ll i = pow(m / (s.front() * 1.0 - 48), 1.0 / (sz(s) - 1)); i > d; i--)
        {
            ll k = 0, b = 1;
            for (ll j = sz(s) - 1; j >= 0; j--, b *= i)
            {
                k += (s[j] - 48) * b;
            }
            if (k <= m)
            {
                c = i;
                break;
            }
        }
        cout << c - d;
        return 0;
    }
    for (ll i = d + 1; i <= pow(m, 1.0 / (sz(s) - 1)); i++)
    {
        ll k = 0, b = 1;
        for (ll j = sz(s) - 1; j >= 0; j--, b *= i)
        {
            k += (s[j] - 48) * b;
        }
        if (k > m)
            break;
        c++;
    }
    cout << c;
    return 0;
}
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
#ifdef ENABLE_DEBUG
#define dump(a) cerr<<#a<<"="<<a<<endl
#define dumparr(a,n) cerr<<#a<<"["<<n<<"]="<<a[n]<<endl
#else
#define dump(a) 
#define dumparr(a,n) 
#endif
#define FOR(i, a, b) for(ll i = (ll)a;i < (ll)b;i++)
#define For(i, a) FOR(i, 0, a)
#define REV(i, a, b) for(ll i = (ll)b-1LL;i >= (ll)a;i--)
#define Rev(i, a) REV(i, 0, a)
#define REP(a) For(i, a)
#define SIGN(a) (a==0?0:(a>0?1:-1))

typedef long long int ll;
typedef unsigned long long ull;
typedef unsigned int uint;
typedef pair<ll, ll> pll;
typedef pair<ll,pll> ppll;
typedef vector<ll> vll;
typedef long double ld;
typedef pair<ld,ld> pdd;

pll operator+(pll a,pll b){
  return pll(a.first+b.first,a.second+b.second);
}
pll operator-(pll a,pll b){
  return pll(a.first-b.first,a.second-b.second);
}
pll operator*(ll a,pll b){
  return pll(b.first*a,b.second*a);
}
const ll INF=(1LL<<60);
#if __cplusplus<201700L
ll gcd(ll a, ll b) {
  a=abs(a);
  b=abs(b);
  if(a==0)return b;
  if(b==0)return a;
  if(a < b) return gcd(b, a);
  ll r;
  while ((r=a%b)) {
    a = b;
    b = r;
  }
  return b;
}
#endif
template<class T>
bool chmax(T& a,const T& b){
  if(a<b){
    a=b;
    return true;
  }
  return false;
}
template<class T>
bool chmin(T& a,const T& b){
  if(a>b){
    a=b;
    return true;
  }
  return false;
}
template<class S,class T>
std::ostream& operator<<(std::ostream& os,pair<S,T> a){
  os << "(" << a.first << "," << a.second << ")";
  return os;
}
template<class T>
std::ostream& operator<<(std::ostream& os,vector<T> a){
  os << "[ ";
  REP(a.size()){
    os<< a[i] << " ";
  }
  os<< " ]";
  return os;
}


void solve(std::string X, long long M){
  if(X.size()==1){
    ll x=stoll(X);
    if(x<=M){
      cout<<1<<endl;
      return;
    }else{
      cout<<0<<endl;
      return;
    }
  }
  ll maxchar=0;
  for (auto &&i : X)
  {
    ll ii=i-'0';
    chmax(maxchar,ii);
  }
  
  ll r=M+1,l=maxchar;
  while(l+1<r){
    ll mid=(l+r)/2;
    ll tmp=0;
    bool f=false;
    for (auto &&i : X)
    {
      ll ii=i-'0';
      if(tmp>(M-ii)/mid){
        f=true;
        break;
      }
      tmp=tmp*mid+ii;
      if(tmp>M){
        f=true;
        break;
      }
    }
    if(f){
      r=mid;
    }else{
      l=mid;
    }
  }
  cout<<l-maxchar<<endl;
}

int main(){
  cout<<setprecision(1000);
  std::string X;
    std::cin >> X;
    long long M;
    scanf("%lld",&M);
  solve(X, M);
  return 0;
}
