#include<iostream>
#include<vector>
#include<set>
#include<algorithm>
 
using namespace std;
 
typedef unsigned long long ll;

ll toNum(char c){
  if(c >= 'A') return c-'A'+10;
  return c-'0';
}

ll convert(const string& s, ll base){
  ll res = 0;
  for(int i = 0; i < (int)s.length(); i++){
    res *= base;
    res += toNum(s[i]);
  }
  return res;
}

vector<int> prime_factor(int n){
  vector<int> res;
  for(int i = 2; i*i <= n; i++){
    while(n % i == 0){
      res.push_back(i);
      n /= i;
    }
  }
  if(n != 1) res.push_back(n);
  sort(res.begin(),res.end());
  return res;
}

ll find(ll num, ll base){
  long double end = num;
  long double now = base;
  ll res = 0;
  ll b = base;
  while(now <= end){
    res += num/b;
    if(num/base+1 < b) break;
    b *= base;
    now *= base;
  }
  return res;
}

vector<int> make(int N){
  vector<int> v = prime_factor(N);
  v.erase(unique(v.begin(),v.end()), v.end());
  return v;
}

int main(){
  int N;
  string M;
  while(cin >> N >> M && N){
    vector<int> v = prime_factor(N);
    vector<int> prime = make(N);
    vector<ll> need(prime.size(), 0);
    
    for(int i = 0; i < (int)prime.size(); i++){
      need[i] = upper_bound(v.begin(),v.end(),prime[i])
	-lower_bound(v.begin(),v.end(),prime[i]);
    }
    
    
    
    vector<ll> have(prime.size(),0);
    ll tmp = convert(M,N);
    for(int i = 0; i < (int)prime.size(); i++){
      have[i] = find(tmp, prime[i]);
    }
    
    for(int i = 0; i < (int)prime.size(); i++) have[i]/=need[i];
    ll ans = have[0];
    for(int i = 0; i < (int)prime.size(); i++) ans = min(ans, have[i]);
    cout << ans << endl;
  }
  return 0;
}
### Prompt

Please provide a cpp coded solution to the problem described below:

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<set>
#include<algorithm>
 
using namespace std;
 
typedef unsigned long long ll;

ll toNum(char c){
  if(c >= 'A') return c-'A'+10;
  return c-'0';
}

ll convert(const string& s, ll base){
  ll res = 0;
  for(int i = 0; i < (int)s.length(); i++){
    res *= base;
    res += toNum(s[i]);
  }
  return res;
}

vector<int> prime_factor(int n){
  vector<int> res;
  for(int i = 2; i*i <= n; i++){
    while(n % i == 0){
      res.push_back(i);
      n /= i;
    }
  }
  if(n != 1) res.push_back(n);
  sort(res.begin(),res.end());
  return res;
}

ll find(ll num, ll base){
  long double end = num;
  long double now = base;
  ll res = 0;
  ll b = base;
  while(now <= end){
    res += num/b;
    if(num/base+1 < b) break;
    b *= base;
    now *= base;
  }
  return res;
}

vector<int> make(int N){
  vector<int> v = prime_factor(N);
  v.erase(unique(v.begin(),v.end()), v.end());
  return v;
}

int main(){
  int N;
  string M;
  while(cin >> N >> M && N){
    vector<int> v = prime_factor(N);
    vector<int> prime = make(N);
    vector<ll> need(prime.size(), 0);
    
    for(int i = 0; i < (int)prime.size(); i++){
      need[i] = upper_bound(v.begin(),v.end(),prime[i])
	-lower_bound(v.begin(),v.end(),prime[i]);
    }
    
    
    
    vector<ll> have(prime.size(),0);
    ll tmp = convert(M,N);
    for(int i = 0; i < (int)prime.size(); i++){
      have[i] = find(tmp, prime[i]);
    }
    
    for(int i = 0; i < (int)prime.size(); i++) have[i]/=need[i];
    ll ans = have[0];
    for(int i = 0; i < (int)prime.size(); i++) ans = min(ans, have[i]);
    cout << ans << endl;
  }
  return 0;
}
```