#include<iostream>
using namespace std;

int main(){
  int n;
  string m;
  while(cin >> n >> m, n||m!="0"){
    long long M = 0,k = 1;
    for(int i=(int)m.size()-1;i>=0;i--){
      if('0'<= m[i] && m[i]<='9')M += (m[i]-'0')*k;
      else M += (m[i]-'A' + 10)*k;
      k *= n;
    }

    int f[11];
    int pr[] = {2,3,5,7,11,13,17,19,23,29,31};
    
    for(int i=0;i<11;i++){
      int tmp = n;
      f[i] = 0;
      while(!(tmp%pr[i])){
	tmp/=pr[i];
	f[i]++;
      }
    }

    long long ans = 1LL<<62;
    for(int i=0;i<11;i++){
      if(f[i]){
	long long tmp = M,sum = 0;
	while(pr[i]<=tmp){
	  sum += tmp/pr[i];
	  tmp /= pr[i];
	}
	ans = min(ans, sum/f[i]);
      }
    }
    cout << ans << endl;
  }
}
### Prompt

Develop a solution in CPP 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>
using namespace std;

int main(){
  int n;
  string m;
  while(cin >> n >> m, n||m!="0"){
    long long M = 0,k = 1;
    for(int i=(int)m.size()-1;i>=0;i--){
      if('0'<= m[i] && m[i]<='9')M += (m[i]-'0')*k;
      else M += (m[i]-'A' + 10)*k;
      k *= n;
    }

    int f[11];
    int pr[] = {2,3,5,7,11,13,17,19,23,29,31};
    
    for(int i=0;i<11;i++){
      int tmp = n;
      f[i] = 0;
      while(!(tmp%pr[i])){
	tmp/=pr[i];
	f[i]++;
      }
    }

    long long ans = 1LL<<62;
    for(int i=0;i<11;i++){
      if(f[i]){
	long long tmp = M,sum = 0;
	while(pr[i]<=tmp){
	  sum += tmp/pr[i];
	  tmp /= pr[i];
	}
	ans = min(ans, sum/f[i]);
      }
    }
    cout << ans << endl;
  }
}
```