#include<bits/stdc++.h>
#define ll long long
using namespace std;
int read()
{
	char c;
	int w=1;
	while((c=getchar())>'9'||c<'0')if(c=='-')w=-1;
	int ans=c-'0';
	while((c=getchar())>='0'&&c<='9')ans=(ans<<1)+(ans<<3)+c-'0';
	return ans*w;
}
char s[61];
ll m;
int n;
ll base[600];
bool check(ll x)
{
	base[1]=1;
	ll nowans=s[1]-'0';
	for(int i=2;i<=n;i++)
	{
		if(1.0*x*base[i-1]>m)return false;
		base[i]=base[i-1]*x;
		if(1.0*(s[i]-'0')*base[i]+nowans>m)return false;
		nowans+=base[i]*(s[i]-'0');
	}
	return true;
}
int main(){
	scanf("%s",s+1);
	cin>>m;
	n=strlen(s+1);
	if(n==1)
	{
		if(m<s[1]-'0')
		{
			puts("0");
			return 0;
		}
		else 
		{
			puts("1");
			return 0;
		}
	}
	reverse(s+1,s+n+1);
	int num=0;
	for(int i=1;i<=n;i++)num=max(num,s[i]-'0');
	ll l=num+1;
	ll r=m;
	ll ans=0;
	if(!check(num+1))
	{
		puts("0");
		return 0;
	}
	while(l<=r)
	{
		ll mid=l+r>>1;
//		cout<<mid<<endl;
		if(check(mid))ans=mid,l=mid+1;
		else r=mid-1;
	}
	cout<<ans-num<<endl;
	return 0;
}
#include <bits/stdc++.h>
#include <cassert>
#define rep(i, n) for (int i = 0; i < (n); i++)
using namespace std;
using ll = long long;
using P = pair<int, int>;
/*
struct Edge
{
  int to;
  int weight;
  Edge(int t, int w) : to(t), weight(w) {}
};
using Graph = vector<vector<Edge>>;
*/
using Graph = vector<vector<int>>;

const long long INF = 1LL << 60;
const int INT_INF = 1000000000;

int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};
// int dx[8] = {-1, -1, -1, 0, 0, 1, 1, 1}, dy[8] = {-1, 0, 1, 1, -1, 1, 0, -1};

bool check(ll x, string X, ll M)
{
  // x進数
  ll sum = 0;
  for (int i = 0; i < X.size(); i++)
  {
    if (sum > M / x)
      return false;
    else
      sum = sum * x + (ll)(X[i] - '0');
  }
  if (sum <= M)
    return true;
  else
    return false;
}
// sum + c, (sum + c) * x + c,... を繰り返す

int main()
{
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  string X;
  cin >> X;
  ll M;
  cin >> M;
  int d = 0;
  for (int i = 0; i < X.size(); i++)
  {
    int now = X[i] - '0';
    d = max(d, now);
  }
  if (X.size() == 1)
  {
    if (M >= d)
      cout << 1 << endl;
    else
      cout << 0 << endl;
    return 0;
  }

  ll left = d, right = M + 10;
  while (left + 1 < right)
  {
    ll mid = (left + right) / 2;
    if (check(mid, X, M))
      left = mid;
    else
      right = mid;
    cerr << "left: " << left << "  right: " << right << endl;
  }
  cout << left - d << endl;
  return 0;
}
