#include <bits/stdc++.h>
typedef long long ll;
typedef long double ld;
#define fr(i, a, b) for (ll i = a; i < b; i++)
#define rf(i, a, b) for (ll i = a; i >= b; i--)
typedef std::vector<long long> vi;
#define F first
#define S second
#define fast                      \
    ios_base::sync_with_stdio(0); \
    cin.tie(0);                   \
    cout.tie(0);
#define mod 1000000007
#define PB push_back
#define MP make_pair
#define PI 3.14159265358979323846
#define all(a) a.begin(), a.end()
#define mx(a) *max_element(all(a))
#define mn(a) *min_element(all(a))
const ll INF = LLONG_MAX / 2;
const ll N = 2e5 + 1;
using namespace std;
ll n, maxid = 0, m;
ll pow1(ll n, ll p)
{
    if (p == 0)
        return 1;
    ll x = pow1(n, p / 2);
    if (x > m || x >= 1000000001)
        return INF;
    x = (x * x);
    if (x > m)
        return INF;
    if (p % 2 == 0)
        return x;
    else
    {
        if (x * n > m)
            return INF;
        return (x * n);
    }
}
string x;
bool check(ll k)
{
    ll j = 0, ans = 0;
    rf(i, n - 1, 0)
    {
        if (pow1(k, j) == INF)
            return false;
        if (pow1(k, j) + ans > m || ans > m)
            return false;
        ans += (pow1(k, j) * ((ll)(x[i] - '0')));
        j++;
    }
    if (ans > m)
        return false;
    return true;
}
int main()
{
    fast;
    ll t = 1;
    // std::cin >> t;
    while (t--)
    {
        cin >> x;
        n = x.length();
        cin >> m;
        if (x.length() == 1)
        {
            ll c = x[0] - '0';
            if (m < c)
                cout << 0 << "\n";
            else
                cout << 1 << "\n";
            continue;
        }
        fr(i, 0, n)
            maxid = max(maxid, (ll)(x[i] - '0'));
        ll l = maxid + 1, r = m + 1;
        // cout << l << "\n";
        // cout << maxid << "\n";
        while (l <= r)
        {
            ll mid = (l + r) / 2;
            if (check(mid))
            {
                l = mid + 1;
            }
            else
            {
                r = mid - 1;
            }
        }
        cout << l - 1 - maxid << "\n";
    }
}

  #include <bits/stdc++.h>
  using namespace std;
  typedef long long ll;
  typedef vector<int> vi;
  typedef pair<int,int> pii;
  #define pii pair<int,int>
  #define fi first
  #define se second

  #define pb push_back
  #define rep(i,n) for (int i=1;i <=int(n);i++)
  #define ffor(i,n) for (int i=0;i <int(n);i++)
  #define all(x) x.begin(),x.end()

  //mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
  //use rng() for random




pii a[200005]; pii b[200005];
  int main(){
       
      ios_base::sync_with_stdio(false);
      cin.tie(NULL);
       int n; cin >> n;
       rep(i,n){ cin >> a[i].fi >> b[i].fi;
            a[i].se = i ; b[i].se = i;}
       map<pii,int> cnt;
       sort(a+1,a+1+n);
       sort(b+1,b+1+n);
       int res = a[n].fi- a[1].fi;
       vector<pair<ll,pii>> ans ;
       int res1 = min(a[n].se,a[1].se); int res2 = max(a[n].se,a[1].se);
       ans.pb({res,{res1,res2}});
       
       
       res = a[n-1].fi - a[1].fi;
         res1 = min(a[n-1].se,a[1].se); res2 = max(a[n-1].se,a[1].se);
           ans.pb({res,{res1,res2}});
       
         res = a[n].fi - a[2].fi;
       res1 = min(a[n].se,a[2].se); res2 = max(a[n].se,a[2].se);
                 ans.pb({res,{res1,res2}});
       swap(a,b);
        res = a[n].fi- a[1].fi;
          
             res1 = min(a[n].se,a[1].se);  res2 = max(a[n].se,a[1].se);
            ans.pb({res,{res1,res2}});
            
            res = a[n-1].fi - a[1].fi;
              res1 = min(a[n-1].se,a[1].se); res2 = max(a[n-1].se,a[1].se);
                ans.pb({res,{res1,res2}});
            
              res = a[n].fi - a[2].fi;
            res1 = min(a[n].se,a[2].se); res2 = max(a[n].se,a[2].se);
                      ans.pb({res,{res1,res2}});
           
       sort(all(ans));
       reverse(all(ans));
       int num=0;
       for (auto p: ans){
            
                 int  a1 = min(p.se.fi,p.se.se);
                 int a2 = max(p.se.fi,p.se.se);
            if (cnt[{a1,a2}]) continue;
            cnt[{a1,a2}]++;
            num++;
            if (num==2){
                 cout << p.fi << '\n'; return 0;
            }
            
       }
       
       
       
        return 0;
  }

 
