#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;
}
### Prompt

Please create a solution in cpp to the following problem:

You are one of ICPC participants and in charge of developing a library for multiprecision numbers and radix conversion. You have just finished writing the code, so next you have to test if it works correctly. You decided to write a simple, well-known factorial function for this purpose:

<image>

Your task is to write a program that shows the number of trailing zeros when you compute M! in base N, given N and M.



Input

The input contains multiple data sets. Each data set is described by one line in the format below:


N M


where N is a decimal number between 8 and 36 inclusive, and M is given in the string repre- sentation in base N. Exactly one white space character appears between them.

The string representation of M contains up to 12 characters in base N. In case N is greater than 10, capital letters A, B, C, ... may appear in the string representation, and they represent 10, 11, 12, ..., respectively.

The input is terminated by a line containing two zeros. You should not process this line.

Output

For each data set, output a line containing a decimal integer, which is equal to the number of trailing zeros in the string representation of M! in base N.

Example

Input

10 500
16 A
0 0


Output

124
2

### Response

```cpp
#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;
}
```