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

int main() {
  cin.tie(nullptr); // Do not flush "cout" when processing "cin".

  string x;
  ll m;
  cin >> x >> m;

  // コーナーケース
  if ((int)x.size() == 1) {
    if (stoi(x) <= m) {
      cout << 1 << endl;
    } else {
      cout << 0 << endl;
    }
    return 0;
  }

  // x に含まれる最も大きい数字 d
  int d = 0;
  for (char c : x) {
    d = max(d, c - '0');
  }

  // 二分探索
  ll ac = d;     // 下限
  ll wa = m + 1; // 上限

  while (wa - ac > 1) {
    // wj = waiting judge
    ll wj = (ac + wa) / 2;

    ll v = 0;
    for (char c : x) {
      // v * wj > m を超えてはいけない
      // 両辺に wj を掛ける
      //
      //   v > (m / wj)
      if (v > (m / wj)) {
        // (v > m) を満たすように、v に適当な値を代入する。
        v = m + 1;
      } else {
        // 文字列 x を reverse する必要がない。
        //
        //   1桁目 --> 0 * wj + (c - '0')
        //   2桁目 --> (c - '0') * wj + (c - '0')
        //   3桁目 --> (c - '0') * wj^2 + (c - '0') * wj^1 + (c - '0')
        v = v * wj + (c - '0');
      }
    }
    if (v <= m) {
      ac = wj;
    } else {
      wa = wj;
    }
  }

  cout << ac - d << endl;
  return 0;
}

#include"bits/stdc++.h"
using namespace std;
using ll=long long;
template<class T=ll>inline T in(istream&is=cin){T ret;is>>ret;return ret;}
template<class T,class Size=typename vector<T>::size_type>inline auto vector_2d(Size h,Size w,T v){return vector<vector<T>>(h,vector<T>(w,v));}
template<class P>struct comp_pair_by_second{bool operator()(const P&p1,const P&p2){return p1.second<p2.second||(p1.second==p2.second&&p1.first<p2.first);}};

int main()
{
    vector<ll>x_v;
    for(auto x:in<string>())x_v.push_back(x-'0');

    const ll m=in();

    if(x_v.size()==1){
        cout<<(x_v[0]<=m?1:0)<<endl;
    }else{
        auto x_leq_m=[x_v,m](ll base){
            vector<ll>m_v;
            for(ll m_c=m;m_c;m_c/=base)m_v.push_back(m_c%base);
            while(m_v.back()==0)m_v.pop_back();
            reverse(m_v.begin(),m_v.end());
            return
                x_v.size()<m_v.size()||
                x_v.size()==m_v.size()&&(
                    lexicographical_compare(x_v.begin(),x_v.end(),m_v.begin(),m_v.end())||
                    equal(x_v.begin(),x_v.end(),m_v.begin())
                );
        };
        if(ll base_min=*max_element(x_v.begin(),x_v.end())+1;!x_leq_m(base_min)){
            cout<<0<<endl;
        }else{
            ll left=base_min,right=numeric_limits<ll>::max();
            while(right-left>1){
                ll base=left+(right-left)/2;
                (x_leq_m(base)?left:right)=base;
            }
            cout<<right-base_min<<endl;
        }
    }
}
