#include <bits/stdc++.h>
using namespace std;

#define ll long long

int main() {
	string X;      //原串 
	ll M;		   //最大 
	cin >> X >> M;
	int n = X.size(); 
	vector<ll> b(n);   //n个向量(已经定型) 每个都是long long  b数组 
	
	ll m = 0;
	for (int i = 0; i < n; i++) {
		b[i] = X[i] - '0';	  //转数字 
		m = max(m, b[i]);     //原串最大的数字 
	}

	auto test = [&](ll N, ll k) {     //把N转k进制 
		vector<ll> a(0);      //向量口袋，虽是0个，但是向量可以扩大 
		while (N > 0) {       //模拟短除(转进制) 
			a.push_back((N % k));
			N /= k;
		}
		reverse(a.begin(), a.end());  //正过来 
		if (a.size() < X.size())      //比原串还短 
			return false;             //滚 
		else if (a.size() > X.size()) //阔以 
			return true;
		else {
			int i = 0;
			while (i<n&& a[i] == b[i]) {        //有多少个相同的数字 
				++i;
			}
			if (i == n)        //全相同 
				return true;
			else if (a[i] < b[i])	  //小于原串 
				return false;
			else
				return true;

		}
	};

	if (n == 1)		//串长度为1 
		cout << (b[0] <= M) ? '1': '0' ;
	else if (!(test(M, m + 1)))
		cout << 0 << endl;
	else {			//二分 
		ll ok = m + 1;  	//左 
		ll ng = M + 1; 		//右 
		ll mid;
		while (ng - ok > 1) {
			mid = (ok + ng) / 2;
			if (test(M, mid))
				ok = mid;
			else
				ng = mid;
		}
		cout << ok - m << endl;

		return 0;
	}
}

#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
#include <climits>
#include <cstring>
#include <cassert>


using namespace std;
//using namespace atcoder;

#define REP(i, n) for (int i=0; i<(n); ++i)
#define RREP(i, n) for (int i=(int)(n)-1; i>=0; --i)
#define FOR(i, a, n) for (int i=(a); i<(n); ++i)
#define RFOR(i, a, n) for (int i=(int)(n)-1; i>=(a); --i)

#define SZ(x) ((int)(x).size())
#define ALL(x) (x).begin(),(x).end()

#define DUMP(x) cerr<<#x<<" = "<<(x)<<endl
#define DEBUG(x) cerr<<#x<<" = "<<(x)<<" (L"<<__LINE__<<")"<<endl;

template<class T>
ostream &operator<<(ostream &os, const vector<T> &v) {
    os << "[";
    REP(i, SZ(v)) {
        if (i) os << ", ";
        os << v[i];
    }
    return os << "]";
}

template<class T, class U>
ostream &operator<<(ostream &os, const pair<T, U> &p) {
    return os << "(" << p.first << " " << p.second << ")";
}

template<class T>
bool chmax(T &a, const T &b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}

template<class T>
bool chmin(T &a, const T &b) {
    if (b < a) {
        a = b;
        return true;
    }
    return false;
}

using ll = long long;
using ull = unsigned long long;
using ld = long double;
using P = pair<int, int>;
using vi = vector<int>;
using vll = vector<ll>;
using vvi = vector<vi>;
using vvll = vector<vll>;

const ll MOD = 1e9 + 7;
const int INF = INT_MAX / 2;
const ll LINF = LLONG_MAX / 2;
const ld eps = 1e-9;


// edit

string X;
ull M;

bool check(ull d) {
    ull val = 0;
    for (auto c : X) {
        if (1. * val * d > 1e18) {
            return false; // too large
        }

        val *= d;
        val += (c - '0');

    }

    return val <= M;
}

void solve() {
    cin >> X >> M;

    ull lb = 1; // ok
    ull ub = M + 1; // ng
    ull tapu;

    if (X.size() == 1) {
        ll val = stoll(X);
        if (val <= M) {
            cout << 1 << endl;
        } else {
            cout << 0 << endl;
        }

        return;
    }


    for (auto c : X) {
        chmax(lb, (ull) c - '0' + 1);
    }

    tapu = lb;
    if (!check(lb)) {
        cout << 0 << endl;
        return;
    }


    while (ub - lb > 1) {
        ull md = (lb + ub) / 2;
        if (check(md)) {
            lb = md;
        } else {
            ub = md;
        }
    }


    ull ans = ub - tapu;
    cout << ans << endl;
}


int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(10);
//    std::ifstream in("input.txt");
//    std::cin.rdbuf(in.rdbuf());

    solve();


    return 0;
}
