#include<iostream>
#include<string>
#include<vector>
#include<cmath>
using namespace std;

typedef long long ll;

void factorize(vector<ll> &p,vector<ll> &cnt,ll x) {
    p.clear(); cnt.clear();
    if(x <= 1) {
        p.push_back(1);
        cnt.push_back(1);
        return;
    }

    ll lim = (ll)sqrt(x);
    ll pp = 2;
    while(true) {
        if(x <= 1) break;
        if(pp > lim) {
            p.push_back(x);
            cnt.push_back(1);
            break;
        }
        if(x % pp == 0) {
            p.push_back(pp);
            cnt.push_back(0);
            while(x%pp == 0) {
                cnt[cnt.size()-1]++;
                x /= pp;
            }
        }
        pp++;
    }
    return;
}

int main() {
    int base;
    string a;
    while(cin>>base>>a, base) {
        unsigned long long m = 0;
        for(int i=0; i<a.length(); ++i) {
            m *= base;
            if(a[i] <= '9') m += a[i] - '0';
            else m += a[i] - 'A' + 10;
        }

        vector<ll> p,cnt;
        factorize(p,cnt,base);

        vector<ll> pp(p.size(), 0);
        for(int i=0; i<p.size(); ++i) {
            ll n = p[i];
            while(n <= m) {
                pp[i] += m/n;
                n *= p[i];
            }
        }

        ll ans = 1ll<<62;
        for(int i=0; i<p.size(); ++i) ans = min(ans, pp[i]/cnt[i]);
        cout<<ans<<endl;
    }
}
### 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<string>
#include<vector>
#include<cmath>
using namespace std;

typedef long long ll;

void factorize(vector<ll> &p,vector<ll> &cnt,ll x) {
    p.clear(); cnt.clear();
    if(x <= 1) {
        p.push_back(1);
        cnt.push_back(1);
        return;
    }

    ll lim = (ll)sqrt(x);
    ll pp = 2;
    while(true) {
        if(x <= 1) break;
        if(pp > lim) {
            p.push_back(x);
            cnt.push_back(1);
            break;
        }
        if(x % pp == 0) {
            p.push_back(pp);
            cnt.push_back(0);
            while(x%pp == 0) {
                cnt[cnt.size()-1]++;
                x /= pp;
            }
        }
        pp++;
    }
    return;
}

int main() {
    int base;
    string a;
    while(cin>>base>>a, base) {
        unsigned long long m = 0;
        for(int i=0; i<a.length(); ++i) {
            m *= base;
            if(a[i] <= '9') m += a[i] - '0';
            else m += a[i] - 'A' + 10;
        }

        vector<ll> p,cnt;
        factorize(p,cnt,base);

        vector<ll> pp(p.size(), 0);
        for(int i=0; i<p.size(); ++i) {
            ll n = p[i];
            while(n <= m) {
                pp[i] += m/n;
                n *= p[i];
            }
        }

        ll ans = 1ll<<62;
        for(int i=0; i<p.size(); ++i) ans = min(ans, pp[i]/cnt[i]);
        cout<<ans<<endl;
    }
}
```