#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)

int main() {
  // 与えられた値を記録する
  // Xは18桁を超えるのでstring型としておく
  // Mは9桁を超え、18桁を超えないのでint64_t型としておく
  string X; cin >> X; int64_t M; cin >> M;
  // Xが1桁の場合は概算時に面倒なので先に算出してしまう(面倒な理由は後述)
  if (X.size() == 1) {
    // Xが1桁の場合は得られる値がXの数字そのものとなる('8'の場合8)
    // これは、Xが何進数であろうとも変わらない
    // そのため、得られる値がM超過であった場合は何進数であろうともMを超える
    // 例：X = '8', M = 7 => 得られる値は常に8なのでM以下の場合は存在しない => 0種類
    // 得られる値がM以下であった場合、何進数であろうともM以下となる
    // なので、n進数のnは無限に存在することになるが、
    // 「得られる値のうち、M以下であるようなものは"何種類"」と聞かれているので
    // 1種類ということになる
    // 例：X = '8', M = 9 => 得られる値は常に8なのでM以下は8の1種類 => 1種類
    cout << (stoll(X) <= M) << endl; return 0;
  }
  // Xに含まれる最も大きい数字dを探索する
  int64_t d = 0;
  rep(i, X.size()) if (d < stoi(string(1, X.at(i)))) {
    d = stoi(string(1, X.at(i)));
  }
  int64_t ans = (int64_t)pow(M / stoi(string(1, X.at(0))), 1 / (double)(X.size() - 1));
  ans = max(d, ans - 1);
  while (true) {
    int64_t temp = 0;
    rep(i, X.size()) {
      if (temp != 0 && temp >= LLONG_MAX / ans) goto BREAK;
      temp = temp * ans + stoi(string(1, X.at(i)));
    }
    if (temp > M) goto BREAK;
    ans++;
  }
BREAK:
  ans = max((int64_t)0, ans - d - 1);
  cout << ans << endl;
}
#include<bits/stdc++.h>

using namespace std;


#define pb push_back
const int maxN = 1e6 + 10;
int n;
string s;
int a[maxN];
vector<int> v[maxN];
unsigned long long m;

int main()
{   
	cin>>s;
	cin>>m;

	assert(s[0]  > '0');

	if (s.size() == 1)
	{
		if (s[0] -'0' <= m) printf("1\n"); else 
		printf("0\n");
		return 0;
	}
   
    unsigned long long lo = 0;
    unsigned long long ro = 2e18 + 10;
	for (int i : s)
		if (lo < i - '0') lo = i - '0';

    unsigned long long d = lo;

	while(lo < ro - 1)
	{
		unsigned long long mid = (lo + ro ) / 2;

       unsigned long long xi = 0;
       
       int bad = 0;
       for (int i : s)
       {
          if (m/mid < xi) {
          	 bad = 1;
          	 break;
          }
       	  xi *= mid;
       	  xi += (i-'0');
       }
       if (bad) ro = mid; else 
       if (xi <= m) lo = mid; else ro = mid;
	}

	cout<<lo - d<<endl;
	return 0;
}