#include <iostream>
#include <algorithm>
#include <string>
#include <map>
#include <fstream>

using namespace std;

typedef unsigned long long ll;
const ll INF=18000000000000000000ULL;

//ifstream ifs("input.txt");
//ofstream ofs("output.txt");
//#define cin ifs
//#define cout ofs

map<int,int> prime_decompos(int a){
	map<int,int> res;
	for(int i=2;i*i<=a;i++){
		if(a%i==0){
			res[i]++;
			a/=i;
			i--;
		}
	}
	if(a!=1)res[a]++;
	return res;
}

int main(){
	int n;
	ll m;
	string str;
	while(cin>>n>>str&&!(n==0&&str=="0")){
		ll mul=1;
		m=0;
		for(int i=str.size()-1;i>=0;i--){
			ll a=str[i]-'0';
			if(str[i]>='A'&&str[i]<='Z')a=10+str[i]-'A';
			m+=a*mul;
			mul*=n;
		}
		map<int,int> np=prime_decompos(n);
		ll res=INF;
		for(map<int,int>::iterator it=np.begin();it!=np.end();it++){
			ll a=it->first;
			int b=it->second;
			ll cnt=0;
			while(a<=m){
				cnt+=(m/a);
				a*=it->first;
			}
			res=min(res,cnt/b);
		}
		cout<<res<<endl;
	}

	return 0;
}
### Prompt

Please create a solution in Cpp 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 <algorithm>
#include <string>
#include <map>
#include <fstream>

using namespace std;

typedef unsigned long long ll;
const ll INF=18000000000000000000ULL;

//ifstream ifs("input.txt");
//ofstream ofs("output.txt");
//#define cin ifs
//#define cout ofs

map<int,int> prime_decompos(int a){
	map<int,int> res;
	for(int i=2;i*i<=a;i++){
		if(a%i==0){
			res[i]++;
			a/=i;
			i--;
		}
	}
	if(a!=1)res[a]++;
	return res;
}

int main(){
	int n;
	ll m;
	string str;
	while(cin>>n>>str&&!(n==0&&str=="0")){
		ll mul=1;
		m=0;
		for(int i=str.size()-1;i>=0;i--){
			ll a=str[i]-'0';
			if(str[i]>='A'&&str[i]<='Z')a=10+str[i]-'A';
			m+=a*mul;
			mul*=n;
		}
		map<int,int> np=prime_decompos(n);
		ll res=INF;
		for(map<int,int>::iterator it=np.begin();it!=np.end();it++){
			ll a=it->first;
			int b=it->second;
			ll cnt=0;
			while(a<=m){
				cnt+=(m/a);
				a*=it->first;
			}
			res=min(res,cnt/b);
		}
		cout<<res<<endl;
	}

	return 0;
}
```