#pragma comment(linker, "/STACK:1024000000,1024000000")
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <ctime>
#include <algorithm>
#include <iostream>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <queue>

using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
#define PB push_back
#define fi first
#define se second
#define MP make_pair
const int P = 1000000007;
const int V = 70;
char s[V];
int a[V];
LL K;

bool check(LL mid, int n) {
    LL v = 0;
    for (int i = 0; i < n; ++i) {
        if (v > K / mid || v * mid > K) return false;
        v = v * mid + a[i];
    }
    return v <= K;
}


int main() {
    while (~scanf("%s%lld", s, &K)) {
        int n = strlen(s);
        for (int i = 0; i < n; ++i) a[i] = s[i] - '0';
        int D = 0;
        for (int i = 0; i < n; ++i) D = max(D, a[i]);
        if (n == 1) {
            if (a[0] <= K) puts("1");
            else puts("0");
            continue;
        }
        if (D > K) {
            puts("0");
            continue;
        }
        LL lo = 1, up = K;
        while (lo != up) {
            LL mid = (lo + up + 1) / 2;
            //printf("%lld %lld %lld\n", lo, up, mid);
            if (check(mid, n)) lo = mid;
            else up = mid - 1;
        }
        printf("%lld\n", max(0LL, up - D));
    }
    return 0;
}

/*
22 10
999 1500
100000000000000000000000000000000000000000000000000000000000 1000000000000000000
*/

#include<bits/stdc++.h> 
using namespace std;
namespace Sakurajima_Mai{
    #define ms(a) memset(a,0,sizeof(a))
    #define repi(i,a,b) for(int i=a,bbb=b;i<=bbb;++i)//attention reg int or reg ll ?
    #define repd(i,a,b) for(int i=a,bbb=b;i>=bbb;--i)
    #define reps(s) for(int i=head[s],v=e[i].to;i;i=e[i].nxt,v=e[i].to)
    #define ce(i,r) i==r?'\n':' '
    #define pb push_back 
    #define all(x) x.begin(),x.end()
    #define gmn(a,b) a=min(a,b)
    #define gmx(a,b) a=max(a,b)
    #define fi first
    #define se second                         
    typedef long long ll;
    typedef unsigned long long ull;
    typedef double db;
    const int infi=2e9;//infi较大，注意涉及inf相加时爆int
    const ll infl=4e18;
    inline ll ceil_div(ll a,ll b){ return (a+b-1)/b; }
    inline ll pos_mod(ll a,ll b){ return (a%b+b)%b; }
    //std::mt19937 rnd(time(0));//std::mt19937_64 rnd(time(0));
}
using namespace Sakurajima_Mai;
namespace Fast_Read{
    inline int qi(){
        int f=0,fu=1; char c=getchar();
        while(c<'0'||c>'9'){ if(c=='-')fu=-1; c=getchar(); }
        while(c>='0'&&c<='9'){ f=(f<<3)+(f<<1)+c-48; c=getchar(); }
        return f*fu;
    }
    inline ll ql(){
        ll f=0;int fu=1; char c=getchar();
        while(c<'0'||c>'9'){ if(c=='-')fu=-1; c=getchar(); }
        while(c>='0'&&c<='9'){ f=(f<<3)+(f<<1)+c-48; c=getchar(); }
        return f*fu;
    }
    inline db qd(){
        char c=getchar();int flag=1;double ans=0;
        while((!(c>='0'&&c<='9'))&&c!='-') c=getchar();
        if(c=='-') flag=-1,c=getchar();
        while(c>='0'&&c<='9') ans=ans*10+(c^48),c=getchar();
        if(c=='.'){c=getchar();for(int Bit=10;c>='0'&&c<='9';Bit=(Bit<<3)+(Bit<<1)) ans+=(double)(c^48)*1.0/Bit,c=getchar();}
        return ans*flag;
    }
}
namespace Read{
    #define si(a) scanf("%d",&a)
    #define sl(a) scanf("%lld",&a)
    #define sd(a) scanf("%lf",&a)
    #define ss(a) scanf("%s",a)
    #define rai(x,a,b) repi(i,a,b) x[i]=qi()
    #define ral(x,a,b) repi(i,a,b) x[i]=ql()
}
namespace Out{
    #define pi(x) printf("%d",x)
    #define pl(x) printf("%lld",x)
    #define ps(x) printf("%s",x)
    #define pc(x) printf("%c",x)
    #define pe() puts("")
}
namespace DeBug{
    #define MARK false
    #define DB if(MARK) 
    #define pr(x) cout<<#x<<": "<<x<<endl
    #define pra(x,a,b) cout<<#x<<": "<<endl; \
            repi(i,a,b) cout<<x[i]<<" ";     \
            puts("");   
    #define FR(a) freopen(a,"r",stdin)
    #define FO(a) freopen(a,"w",stdout)
}
using namespace Fast_Read;
using namespace Read;
using namespace Out;
using namespace DeBug;
namespace INT128{
    inline void print(__int128 x)
    {
        if(!x) return;
        if(x<0) putchar('-'),x=-x;
        print(x/10),putchar(x%10+'0');
    }
    inline void read(__int128 &X)
    {
        int w=0; char ch=0; X=0;
        while(!isdigit(ch)) w|=ch=='-',ch=getchar();
        while(isdigit(ch)) X=(X<<3)+(X<<1)+(ch^48),ch=getchar();
        if(w) X=-X;
    }
}
using namespace INT128;
const int MAX_N=1e5+5;
char s[MAX_N];
int x[MAX_N],len;
__int128 m;
bool check(ll base)
{
    __int128 now=1,res=0;
    repd(i,len,1){
        if(res>m-now*x[i]) return false;
        res+=now*x[i];
        if(i!=1&&now>m/base) return false;
        now*=base;
        if(i!=1&&now>m) return false;
    }
    return true;
}
int main()
{
    ss(s+1); read(m);
    len=strlen(s+1);
    int mx=0;
    repi(i,1,len) x[i]=(s[i]-'0'),gmx(mx,x[i]);
    if(!check(1ll*mx+1)) return puts("0"),0;
    if(len==1) return puts("1"),0;
    ll l=mx+1,r=1000000000000000000,ans;
    while(l<=r){
        ll mid=(l+r)>>1;
        if(check(mid)) ans=mid,l=mid+1;
        else r=mid-1;
    }
    pl(ans-(mx+1)+1),pe();
    return 0;
}