#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <memory.h>
#include <queue>
#include <cstdio>
#include <cstdlib>
#include <map>
#include <cmath>
using namespace std;

#define rep(i, n) for(int i = 0; i< n; i++)
typedef unsigned long long ll;
typedef pair<int, int> P;
const ll LM = 1LL<<63;

ll tonum(string s, int N){
  ll res = 0;
  int n = s.size();
  rep(i, n){
    ll m = (isdigit(s[i])) ? s[i] - '0' : s[i] - 'A' + 10;
    res = res * (ll)N + m;
  }
  return res;
}

ll get_cnt(ll M, ll i, ll cnt){
  ll res = 0;
  ll num = 1;
  while(num < LM / i){
    num *= i;
    res += M / num;
  }
  return res / cnt;
}

int main(){
  ll N, M;
  string s;
  while(cin >> N >> s && (N || s != "0")){
    M = tonum(s,N);
    ll res = LM;
    for(ll i = 2; i * i <= N; i++){
      if(N%i == 0){
	ll cnt = 0;
	while(N % i == 0) {
	  cnt++;
	  N /= i;
	}
	res = min(res, get_cnt(M, i, cnt));
      }
    }
    if(N > 1) res = min(res, get_cnt(M, N, 1));
    cout << res << 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 <algorithm>
#include <vector>
#include <string>
#include <memory.h>
#include <queue>
#include <cstdio>
#include <cstdlib>
#include <map>
#include <cmath>
using namespace std;

#define rep(i, n) for(int i = 0; i< n; i++)
typedef unsigned long long ll;
typedef pair<int, int> P;
const ll LM = 1LL<<63;

ll tonum(string s, int N){
  ll res = 0;
  int n = s.size();
  rep(i, n){
    ll m = (isdigit(s[i])) ? s[i] - '0' : s[i] - 'A' + 10;
    res = res * (ll)N + m;
  }
  return res;
}

ll get_cnt(ll M, ll i, ll cnt){
  ll res = 0;
  ll num = 1;
  while(num < LM / i){
    num *= i;
    res += M / num;
  }
  return res / cnt;
}

int main(){
  ll N, M;
  string s;
  while(cin >> N >> s && (N || s != "0")){
    M = tonum(s,N);
    ll res = LM;
    for(ll i = 2; i * i <= N; i++){
      if(N%i == 0){
	ll cnt = 0;
	while(N % i == 0) {
	  cnt++;
	  N /= i;
	}
	res = min(res, get_cnt(M, i, cnt));
      }
    }
    if(N > 1) res = min(res, get_cnt(M, N, 1));
    cout << res << endl;
  }
  return 0;

}
```