
/**
* For the brave souls who get this far: You are the chosen ones,
* the valiant knights of programming who toil away, without rest,
* fixing our most awful code. To you, true saviors, kings of men,
* I say this: never gonna give you up, never gonna let you down,
* never gonna run around and desert you. Never gonna make you cry,
* never gonna say goodbye. Never gonna tell a lie and hurt you.
*/

#include<bits/stdc++.h>
         
#define pb push_back
#define nw cout<<"\n";
#define srt(v) sort((v).begin(),(v).end())
#define rvrs(v) reverse((v).begin(),(v).end())
#define mpr make_pair
#define mt make_tuple
#define loop(i,j,n) for (int i = j; i < n; ++i)
#define loop1(i,j,n) for(int i=j;i<=n;++i) 
#define wis(x) std::cerr << #x << " is " << x << std::endl;
         
using namespace std;
         
typedef long long  ll; 



int main ( void )
{                 
                            time_t Time;
                            time(&Time);
                         cerr<<ctime(&Time);
                     ios_base::sync_with_stdio(false);
                       cin.tie(NULL),cout.tie(NULL);
                             cout<<fixed;
            auto starttime=chrono::steady_clock::now();
        
        string str;
        cin >> str;
        ll m;
        cin>> m;
       ll d=*max_element(str.begin(),str.end())-'0';
        
       if(str.size()==1) {
	    if(d<=m)
	     cout<< 1;
	    else
	     cout<<0;
	   }
	   
	   else {
	    ll first = d+1, last = (ll)1e18;
	    
	     while(first<=last) {
			 __int128 number =0;
	    __int128 mid=(first+last)/2;
	    
		for(int i=0;i<(int)str.size();i++) {
		   number*= mid;
		   number+=str[i]-'0';
		   if(number > m)
		      break;
	       } 
	        if(number<=m)
		   first = mid+1;
		  else 
		   last = mid-1;	   
		  }  
    cout<< last - d;
	   }

         
           auto endtime=chrono::steady_clock::now();  
           cerr<<endl<<"Elapsed Time: "
               	 <<chrono::duration_cast<chrono::milliseconds> (endtime-starttime).count()
        	      <<" milliseconds"<<endl;
  return 0;
}

#pragma GCC optimize ("Ofast")
#include<bits/stdc++.h>
#define int long long
using namespace std;
inline int read()
{
	bool flag=1;
	int x=0;
	char c=getchar();
	while(c<'0'||c>'9')
	{
		if(c=='-')
			flag=0;
		c=getchar();
	}
	while(c>='0'&&c<='9')
	{
		x=(x<<1)+(x<<3)+c-'0';
		c=getchar();
	}
	return (flag?x:~(x-1));
}
string s;
int k,maxx;
vector<int> v;
bool judge(__int128 x)
{
	__int128 ans=0;
	for(int i:v)
	{
		ans=ans*x+i;
		if(ans>k)
			return 0;
	}
	return 1;
}
signed main()
{
	cin>>s;
	for(int i=0;i<s.size();i++)
	{
		v.push_back(s[i]-'0');
		maxx=max(maxx,(long long)s[i]-'0');
	}
	cin>>k;
	if(v.size()==1)
	{
		cout<<(v[0]<=k);
		return 0;
	}
	int l=maxx+1;
	int r=2e18;
	while(l<=r)
	{
		__int128 mid=(l+r)>>1;
		if(judge(mid))
			l=mid+1;
		else
			r=mid-1;
	}
	cout<<(l-maxx-1);
	return 0;
}
