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

int main(){
    //freopen("1.in","r",stdin);
    //ios::sync_with_stdio(false);
    char X[66];
    ll M;
    scanf("%s",X);cin>>M;
    int n=strlen(X);
    int max=0;
    for(int i=0;i<n;i++){
      if(X[i]-'0'>max)max=X[i]-'0';
    }
    
    ll count=0;
    
    // for(int base=max+1;;base++){
    //   //cout<<base<<endl;
    //   ll res=0;
    //   int flag=0;
    //   for(int i=0;i<n;i++){
    //     res=res*base+X[i]-'0';
    //     if(res>M){break;flag=1;}
    //   }
    //   //cout<<res<<endl;
    //   if(flag==0){
    //     if(res<=M)count++;else break;
    //   }else break;
    // }
    if(n==1) {
    ll base=max+1;
    __int128 res=0;
      int flag=0;
      for(int i=0;i<1;i++){
        res=res*base+X[i]-'0';
        if(res>M){flag=1;break;}
      }
      //cout<<res<<endl;
      if(flag==0){
        if(res<=M)count++;else {cout<<0;return 0;}
      }else {cout<<0;return 0;}
      cout<<1;




    }
    else 
    {ll base=max+1;
    __int128 res=0;
      int flag=0;
      for(int i=0;i<n;i++){
        res=res*base+X[i]-'0';
        if(res>M){flag=1;break;}
      }
      //cout<<res<<endl;
      if(flag==0){
        if(res<=M)count++;else {cout<<0;return 0;}
      }else {cout<<0;return 0;}
    ll l=max,r=M+1;
    while(l<=r){
      ll mid=l+r>>1;
      ll base=mid;
      __int128 res=0;
      int flag=0;
      for(int i=0;i<n;i++){
        res=res*base+X[i]-'0';
        if(res>M){flag=1;break;}
      }
      //cout<<res<<endl;
      if(flag==0){
        if(res<=M)l=mid+1;else {r=mid-1;}
      }else {r=mid-1;}
    }
    count+=(r-max-1);
    cout<<count;}
}

//{{{
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
using VLL = vector<LL>;
using vi = vector<int>;
using pii = pair<int, int>;
#define sz(x) (int)((x).size())
#define all(x) (x).begin(), (x).end()
#define clr(a, b) memset(a, b, sizeof(a))
#ifdef LOCAL
#include "prettyprint.hpp"
// clang-format off
void _print() { cerr << "]\033[0m\n"; }
template <typename T> void __print(T x) { cerr << x; }
template <typename T, typename... V> void _print(T t, V... v) { __print(t); if (sizeof...(v)) cerr << ", "; _print(v...); }
#define debug(x...) cerr << "\033[1;34m[" << #x << "] = \033[1;32m["; _print(x)
#define debug_arr(x...) cerr << "\033[1;34m[" << #x << "] = \033[1;32m" << (x) << "\033[0m\n"
#else
#define debug(x...)
#define debug_arr(x...)
#endif
// clang-format on
//}}}

string x;
LL m;

bool check(LL base)
{
    __int128 b = base;
    __int128 v = 1;
    __int128 res = 0;
    __int128 mm = __int128(m);

    int n = sz(x);
    for (int i = 0; i < n; i++)
    {
        __int128 dig = x[i] - '0';
        if (v > m) return false;

        res += dig * v;
        v *= b;
    }

    return res <= mm;
}

int main()
{
#ifdef LOCAL
    freopen("in", "r", stdin);
    // freopen("out", "w", stdout);
#endif

    while (cin >> x >> m)
    {
        int mx = -1;
        reverse(all(x));
        for (auto ch : x)
        {
            int d = ch - '0';
            mx = max(mx, d);
        }

        if (check(mx + 1) == false)
        {
            cout << 0 << endl;
            continue;
        }

        LL lo = mx + 1, hi = 3e18 + 100;
        while (lo + 1 < hi)
        {
            LL mid = lo + (hi - lo) / 2;
            bool ok = check(mid);
            if (ok) lo = mid;
            else
                hi = mid;
        }

        debug(lo, hi);

        if (lo >= 2e18)
        {
            cout << 1 << endl;
        }
        else
        {
            cout << lo - (mx + 1) + 1 << endl;
        }
    }

    return 0;
}