#include <bits/stdc++.h>

using namespace std;

int n, d;
long long m;
char s[1005];

int debug() {
    int res = 0;
    bool gg = 0;
    for (int base = d + 1; ; base++) {
        long long num = 0LL;
        for (int i = 0; i < n; i++) {
            if (num > (m - (s[i] - '0')) / base) {
                gg = 1;
                break;
            }
            num = num * base + (s[i] - '0');
        }
        if (gg) break;
        res++;
    }
    return res;
}

int main() {
    scanf("%s", s);
    scanf("%lld", &m);

    n = strlen(s);

    for (int i = 0; i < n; i++) {
        d = max(d, s[i] - '0');
    }

    if (n == 1) {
        if (s[0] - '0' <= m) printf("1\n");
        else printf("0\n");
    }
    else if (n == 2) {
        printf("%lld\n", max(0LL, (m - (s[1] - '0')) / (s[0] - '0') - d));
    }
    else if (n == 3) {
        double a = (s[0] - '0');
        double b = (s[1] - '0');
        double c = (s[2] - '0') - m;
        double delta = b * b - 4.0 * a * c;
        if (delta < 0) return 0 * printf("0\n");
        double rt1 = (-b + sqrt(delta)) / (2.0 * a);
        long long lim = (long long)rt1;
        printf("%lld\n", max(0LL, lim - d));
    }
    else {
        int res = 0;
        bool gg = 0;
        for (int base = d + 1; ; base++) {
            long long num = 0LL;
            for (int i = 0; i < n; i++) {
                if (num > (m - (s[i] - '0')) / base) {
                    gg = 1;
                    break;
                }
                num = num * base + (s[i] - '0');
            }
            if (gg) break;
            res++;
        }
        printf("%d\n", res);
    }
}
#include <bits/stdc++.h>
using namespace std;

int main()
{
    string x; cin>>x;
    long long m; cin>>m;
    vector<long long> x1,x2;
    bool flag=true;
    for (int i = 0; i < x.length(); i++) x1.push_back(x[i]-'0');
    long long n=*max_element(x1.begin(),x1.end());
    n++;
    long long m1=m;
    while (m1>0) {x2.push_back(m1%n); m1/=n;}
    reverse(x2.begin(),x2.end());
    if (x1.size()>x2.size()) {cout<<0<<endl; return 0;}
    else if (x1.size()==x2.size())
    {
        for (int i = 0; i < x2.size(); i++)
        {
            if (x1[i]>x2[i]) {cout<<0<<endl; return 0;}
            else if (x1[i]<x2[i]) break;
        }
    }
    if (x.size()==1) {cout<<1<<endl; return 0;}
    while (flag)
    {
        vector<long long> x3;
        n*=2; m1=m; flag=true;
        while (m1>0) {x3.push_back(m1%n); m1/=n;}
        reverse(x3.begin(),x3.end());
        if (x1.size()>x3.size()) flag=false;
        else if (x1.size()==x3.size())
        {
            for (int i = 0; i < x3.size(); i++)
            {
                if (x1[i]>x3[i]) flag=false;
                else if (x1[i]<x3[i]) break;
            }
        }
    }
    long long n1=n/2;
    while (n-n1>1)
    {
        long long n2=(n+n1)/2; m1=m; vector<long long> x3;
        while (m1>0) {x3.push_back(m1%n2); m1/=n2;}
        reverse(x3.begin(),x3.end());
        if (x1.size()>x3.size()) n=n2;
        else if (x1.size()==x3.size())
        {
            flag=true;
            for (int i = 0; i < x3.size(); i++)
            {
                if (x1[i]>x3[i]) {n=n2; flag=false;}
                else if (x1[i]<x3[i]) break;
            }
            if (flag) n1=n2;
        }
        else n1=n2;
    }
    long long ans=n1-*max_element(x1.begin(),x1.end());
    cout<<ans<<endl;
}