#include<iostream>
#include<string>
#define rep(i,n) for(int i=0;i<n;i++)
using namespace std;
typedef unsigned long long ll;
int p[]={2,3,5,7,11,13,17,19,23,29,31};
int main(){
	int n,nfac[11];
	ll m,fac[11];
	string b;
	while(cin>>n>>b,n){
		m=0;
		rep(i,11)nfac[i]=fac[i]=0;
		rep(i,b.size())m*=n,m+=('0'<=b[i]&&b[i]<='9'?b[i]-'0':b[i]-'A'+10);
		ll ans=1184595334580404209LL;
		rep(i,11){
			while(n%p[i]==0)n/=p[i],nfac[i]++;
			if(nfac[i]){
				for(ll j=p[i];j<=m;j*=p[i])fac[i]+=m/j;
				if(ans>fac[i]/nfac[i])ans=fac[i]/nfac[i];
			}
		}
		cout<<ans<<endl;
	}
	return 0;
}
### Prompt

Your task is to create 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<iostream>
#include<string>
#define rep(i,n) for(int i=0;i<n;i++)
using namespace std;
typedef unsigned long long ll;
int p[]={2,3,5,7,11,13,17,19,23,29,31};
int main(){
	int n,nfac[11];
	ll m,fac[11];
	string b;
	while(cin>>n>>b,n){
		m=0;
		rep(i,11)nfac[i]=fac[i]=0;
		rep(i,b.size())m*=n,m+=('0'<=b[i]&&b[i]<='9'?b[i]-'0':b[i]-'A'+10);
		ll ans=1184595334580404209LL;
		rep(i,11){
			while(n%p[i]==0)n/=p[i],nfac[i]++;
			if(nfac[i]){
				for(ll j=p[i];j<=m;j*=p[i])fac[i]+=m/j;
				if(ans>fac[i]/nfac[i])ans=fac[i]/nfac[i];
			}
		}
		cout<<ans<<endl;
	}
	return 0;
}
```