//Codeforcesで128bit整数を使いたいとき
//→__int128_tを使う&GNU C++17 (64)で提出する

//インクルードなど
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

//イテレーション
#define REP(i,n) for(ll i=0;i<ll(n);i++)
#define REPD(i,n) for(ll i=n-1;i>=0;i--)
#define FOR(i,a,b) for(ll i=a;i<=ll(b);i++)
#define FORD(i,a,b) for(ll i=a;i>=ll(b);i--)
#define FORA(i,I) for(const auto& i:I)
//x:コンテナ
#define ALL(x) x.begin(),x.end() 
#define SIZE(x) ll(x.size()) 
//定数
#define INF32 2147483647 //2.147483647×10^{9}:32bit整数のinf
#define INF64 9223372036854775807 //9.223372036854775807×10^{18}:64bit整数のinf
#define MOD 1000000007 //問題による
//略記
#define F first
#define S second
//出力(空白区切りで昇順に)
#define coutALL(x) for(auto i=x.begin();i!=--x.end();i++)cout<<*i<<" ";cout<<*--x.end()<<endl;

//aをbで割る時の繰上げ,繰り下げ
ll myceil(ll a,ll b){return (a+(b-1))/b;}
ll myfloor(ll a,ll b){return a/b;}

// bool isOK(string X,ll base,ll M) {
//   ll sum = 0;
//   REP(i, X.size()) {
//     if (sum > M / base) {
//       return false;
//     }
//     sum *= base;
//     sum += (X.at(i) - '0');
//   }
 
//   if (sum <= M) {
//     return true;
//   } else {
//     return false;
//   }
// }

bool isOK(string X, ll key,ll M) {
    ll result=0,d = 1;
    
    for(ll i=X.size()-1;i >= 0;i--,d*=key){
        if (M/d < (X[i]-'0')) return false;
        if (result > M - (X[i]-'0')*d) return false;
        result += (X[i]-'0')*d;
        if(i >= 1){
            if(M/key < d){
                return false;
            }
        }
    }
    //cout << "result = " << result << "\n";
    if (result <= M) return true;
    else return false;
}

int main(){
    string X;
    ll M;
    ll max;

    cin >> X >> M;

    max = X[0] - '0';
    for (ll i = 1; i < (ll)X.size(); i++) {
        if (max < X[i] - '0') {
            max = X[i] - '0';
        }
    }
    ll left = M+10, right = max;
    ll mid=0;

    if(X.size()==1){
        if (X[0]-'0' <= M) cout << 1 << "\n";
        else cout << 0 << "\n";
        return 0;
    }

    while(left - right > 1){
        mid = (left + right) / 2;
        //cout << "L R = " << left << " " << right << "\n";
        //cout << "mid = " << mid << "\n";
        if(isOK(X,mid,M)) right = mid;
        else left = mid;
    }
    cout << right - max << "\n";
    return 0;
}
#pragma GCC optimize("Ofast", "unroll-loops")

#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define ld long double

void iosetup(void){
    ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
}

int get_d(string& X){
    int ret = 0;
    for (auto d : X)
        ret = max(ret, (int)(d - '0'));
    return ret;
}

constexpr ll INF = (1LL << 61);

ll n_num(string& X, ll n){
    ll ret = 0LL;
    for (auto d : X){
        if (ret > INF / n) return INF;
        ret = ret * n + (ll)(d - '0');
    }
    return ret;
}

ll solve(string& X, ll M){
    int d = get_d(X);
    if (n_num(X, d + 1) > M) return 0;
    ll ok = d + 1, ng = INF;
    while (ng - ok > 1){
        ll mid = (ok + ng) / 2;
        if (n_num(X, mid) > M) ng = mid;
        else ok = mid;
    }
    return (ng - d - 1);
}

int main(void){
    iosetup();
    string X;
    ll M;
    cin >> X >> M;
    if (X == "1") cout << 1 << endl;
    else if (X.length() == 1){
        ll Xi = (ll)(X[0] - '0');
        if (Xi <= M) cout << 1 << endl;
        else cout << 0 << endl;
    }
    else cout << solve(X, M) << endl;
    return 0;
}