#include<string>
#include<iostream>

using namespace std;

typedef	unsigned long long	ull;

int main(){
	int f[128];
	for(int i='0';i<='9';i++)	f[i]=i-'0';
	for(int i='A';i<='Z';i++)	f[i]=i-'A'+10;

	int base;
	string s;
	for(;cin>>base>>s,base;){
		ull num=0;
		for(int i=0;i<s.length();i++)	num=num*base+f[s[i]];

		const int p[]={31,29,23,19,17,13,11,7,5,3,2};
		int pcnt[11]={};
		for(int b=base,i=0;b>1;){
			if(b%p[i]==0)	b/=p[i],pcnt[i]++;
			else	i++;
		}

		ull zcnt=1ULL<<63;
		for(int i=0;i<11;i++){
			if(pcnt[i]>0){
				ull num2=num,zcnt2=0;
				while(num2)	zcnt2+=num2/p[i],num2/=p[i];
				zcnt=min(zcnt,zcnt2/pcnt[i]);
			}
		}
		cout<<zcnt<<endl;
	}

	return 0;
}
### Prompt

Your challenge is to write a CPP solution 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<string>
#include<iostream>

using namespace std;

typedef	unsigned long long	ull;

int main(){
	int f[128];
	for(int i='0';i<='9';i++)	f[i]=i-'0';
	for(int i='A';i<='Z';i++)	f[i]=i-'A'+10;

	int base;
	string s;
	for(;cin>>base>>s,base;){
		ull num=0;
		for(int i=0;i<s.length();i++)	num=num*base+f[s[i]];

		const int p[]={31,29,23,19,17,13,11,7,5,3,2};
		int pcnt[11]={};
		for(int b=base,i=0;b>1;){
			if(b%p[i]==0)	b/=p[i],pcnt[i]++;
			else	i++;
		}

		ull zcnt=1ULL<<63;
		for(int i=0;i<11;i++){
			if(pcnt[i]>0){
				ull num2=num,zcnt2=0;
				while(num2)	zcnt2+=num2/p[i],num2/=p[i];
				zcnt=min(zcnt,zcnt2/pcnt[i]);
			}
		}
		cout<<zcnt<<endl;
	}

	return 0;
}
```