#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdlib>

using namespace std;

long long N, M;

long long count(int n) {
    long long total = 0;
    long long m = M;
    while (m >= n) {
        total += (m / n);
        m /= n;
    }
    return total;
}

long long to_l(string s) {
    long long n = 0;
    for (int i = 0; i < s.size(); i++) {
        if (isdigit(s[i])) {    
            n = n * N + (s[i] - '0');
        } else {
            n = n * N + (s[i] - 'A' + 10);
        }
    }
    return n;
}

int main() {
    string M_;
    while (cin >> N >> M_) {
        if (N == 0 && M_ == "0") break;
        M = to_l(M_);
        long long ans = 0;
        switch (N) {
            case 8:
                ans = count(2) / 3;
                break;
            case 9:
                ans = count(3) / 2;
                break;
            case 10:
                ans = min(count(2), count(5));
                break;
            case 11:
                ans = count(11);
                break;
            case 12:
                ans = min(count(2) / 2, count(3));
                break;
            case 13:
                ans = count(13);
                break;
            case 14:
                ans = min(count(2), count(7));
                break;
            case 15:
                ans = min(count(3), count(5));
                break;
            case 16:
                ans = count(2) / 4;
                break;
            case 17:
                ans = count(17);
                break;
            case 18:
                ans = min(count(2), count(3) / 2);
                break;
            case 19:
                ans = count(19);
                break;
            case 20:
                ans = min(count(2)/2, count(5));
                break;
            case 21:
                ans = min(count(3), count(7));
                break;
            case 22:
                ans = min(count(2), count(11));
                break;
            case 23:
                ans = count(23);
                break;
            case 24:
                ans = min(count(2) / 3, count(3));
                break;
            case 25:
                ans = count(5) / 2;
                break;
            case 26:
                ans = min(count(2), count(13));
                break;
            case 27:
                ans = count(3) / 3;
                break;
            case 28:
                ans = min(count(2) / 2, count(7));
                break;
            case 29:
                ans = count(29);
                break;
            case 30:
                ans = min(min(count(2), count(3)), count(5));
                break;
            case 31:
                ans = count(31);
                break;
            case 32:
                ans = count(2) / 5;
                break;
            case 33:
                ans = min(count(3), count(11));
                break;
            case 34:
                ans = min(count(2), count(17));
                break;
            case 35:
                ans = min(count(5), count(7));
                break;
            case 36:
                ans = min(count(2) / 2, count(3) / 2);
                break;
        }
        cout << ans << endl;
//        for (int i = 0; i < 36; i++) {
//            cout << count(i) << ' ';
//        }
//        cout << endl;
    }
    return 0;
}

Measured memory_bytes: 928