#include<stdio.h>
#include<algorithm>
using namespace std;
char str[30];
int p[30];
int q[30];
int main(){
	int a;
	while(scanf("%d%s",&a,str),a){
		int b=a;
		int sz=0;
		for(int i=0;i<30;i++)q[i]=0;
		for(int i=2;i*i<=b;i++){
			if(b%i==0){
				p[sz++]=i;
				while(b%i==0){
					b/=i;
					q[sz-1]++;
				}
			}
		}
		if(b>1){p[sz++]=b;q[sz-1]=1;}
		long long val=0;
		for(int i=0;str[i];i++){
			val*=a;
			if(str[i]>='A'&&str[i]<='Z')val+=str[i]-'A'+10;
			else val+=str[i]-'0';
		}
		long long ret=(1LL<<62);
		for(int i=0;i<sz;i++){
			long long tmp=0;
			long long now=val;
			while(now){
				tmp+=now/p[i];
				now/=p[i];
			}
			ret=min(ret,tmp/q[i]);
		}
		printf("%lld\n",ret);
	}
}
### 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<algorithm>
using namespace std;
char str[30];
int p[30];
int q[30];
int main(){
	int a;
	while(scanf("%d%s",&a,str),a){
		int b=a;
		int sz=0;
		for(int i=0;i<30;i++)q[i]=0;
		for(int i=2;i*i<=b;i++){
			if(b%i==0){
				p[sz++]=i;
				while(b%i==0){
					b/=i;
					q[sz-1]++;
				}
			}
		}
		if(b>1){p[sz++]=b;q[sz-1]=1;}
		long long val=0;
		for(int i=0;str[i];i++){
			val*=a;
			if(str[i]>='A'&&str[i]<='Z')val+=str[i]-'A'+10;
			else val+=str[i]-'0';
		}
		long long ret=(1LL<<62);
		for(int i=0;i<sz;i++){
			long long tmp=0;
			long long now=val;
			while(now){
				tmp+=now/p[i];
				now/=p[i];
			}
			ret=min(ret,tmp/q[i]);
		}
		printf("%lld\n",ret);
	}
}
```