#include<iostream>
#include<vector>
#include<climits>
using namespace std;
typedef long long ll;
#define inRange(x,a,b) (a <= x && x <= b)

int main(){
    int n;
    string m;
    vector<int> p({2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31});
    while(cin >> n >> m, n){
        vector<int> base(11, 0);
        vector<ll> cnt(11, 0);
        int cp = n;
        for(int i = 0; i < 11; i++){
            while(cp%p[i] == 0)  base[i]++, cp /= p[i];
        }
        ll val = 0;
        for(int i = 0; i < m.length(); i++){
            val *= n;
            if(inRange(m[i],'0','9'))   val += m[i]-'0';
            else                        val += 10+m[i]-'A';
        }
        for(int i = 0; i < 11; i++){
            ll x = val;
            while(x){
                cnt[i] += x/p[i];
                x /= p[i];
            }
        }

        ll ans = LLONG_MAX;
        for(int i = 0; i < 11; i++){
            if(base[i] == 0)    continue;
            ans = min(ans, cnt[i]/base[i]);
        }
        cout << ans << endl;
    }
    return 0;
}


### Prompt

Create a solution in CPP for 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<vector>
#include<climits>
using namespace std;
typedef long long ll;
#define inRange(x,a,b) (a <= x && x <= b)

int main(){
    int n;
    string m;
    vector<int> p({2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31});
    while(cin >> n >> m, n){
        vector<int> base(11, 0);
        vector<ll> cnt(11, 0);
        int cp = n;
        for(int i = 0; i < 11; i++){
            while(cp%p[i] == 0)  base[i]++, cp /= p[i];
        }
        ll val = 0;
        for(int i = 0; i < m.length(); i++){
            val *= n;
            if(inRange(m[i],'0','9'))   val += m[i]-'0';
            else                        val += 10+m[i]-'A';
        }
        for(int i = 0; i < 11; i++){
            ll x = val;
            while(x){
                cnt[i] += x/p[i];
                x /= p[i];
            }
        }

        ll ans = LLONG_MAX;
        for(int i = 0; i < 11; i++){
            if(base[i] == 0)    continue;
            ans = min(ans, cnt[i]/base[i]);
        }
        cout << ans << endl;
    }
    return 0;
}


```