#include <stdio.h>
#include <cmath>
#include <algorithm>
#include <stack>
#include <queue>
#include <vector>

using namespace std;

int main(){

	long long int number,ans,table[37],work,tmp;
	int base;
	char exp[13];

	while(true){
		scanf("%d %s",&base,exp);
		if(base == 0 && exp[0] == '0')break;

		for(int i = 0; i <= base; i++)table[i] = 0;

		work = base;
		for(int i = 2; i <= base; i++){
			while(work%i == 0){
				table[i]++;
				work /= i;
			}
		}

		number = 0;

		for(int i = 0; exp[i] != '\0'; i++){
			if(exp[i] >= '0' && exp[i] <= '9'){
				number = base*number + (exp[i] - '0');
			}else{
				number = base*number + (10+(exp[i] - 'A'));
			}
		}

		ans = 9223372036854775807;
		for(int i = 2; i <= base; i++){
			if(table[i] > 0){
				work = 0;
				tmp = number;
				while(tmp > 0){
					work += tmp/i;
					tmp /= i;
				}
				work /= table[i];
				ans = min(ans,work);
			}
		}

		printf("%lld\n",ans);
	}
    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 <stdio.h>
#include <cmath>
#include <algorithm>
#include <stack>
#include <queue>
#include <vector>

using namespace std;

int main(){

	long long int number,ans,table[37],work,tmp;
	int base;
	char exp[13];

	while(true){
		scanf("%d %s",&base,exp);
		if(base == 0 && exp[0] == '0')break;

		for(int i = 0; i <= base; i++)table[i] = 0;

		work = base;
		for(int i = 2; i <= base; i++){
			while(work%i == 0){
				table[i]++;
				work /= i;
			}
		}

		number = 0;

		for(int i = 0; exp[i] != '\0'; i++){
			if(exp[i] >= '0' && exp[i] <= '9'){
				number = base*number + (exp[i] - '0');
			}else{
				number = base*number + (10+(exp[i] - 'A'));
			}
		}

		ans = 9223372036854775807;
		for(int i = 2; i <= base; i++){
			if(table[i] > 0){
				work = 0;
				tmp = number;
				while(tmp > 0){
					work += tmp/i;
					tmp /= i;
				}
				work /= table[i];
				ans = min(ans,work);
			}
		}

		printf("%lld\n",ans);
	}
    return 0;
}
```