#include <iostream>
#include <map>
#include <climits>
#include <string>
using namespace std;

unsigned long long to(string w , int base){
	unsigned long long ans = 0;
	for(int i = 0 ; i < w.size() ; i++) ans = ans * base + (w[i] >= 'A' ? w[i] - 'A' + 10 : w[i] - '0');
	return ans;
}

map<int,int> factor(int n){
	map<int,int> w;
	for(int i = 2 ; i*i<=n ; i++)
		while(n%i==0) w[i]++ , n /= i;
	if(n!=1) w[n]++;
	return w;
}

int main(){
	int n;
	string m;
	while(cin >> n >> m, n){
		unsigned long long v = to(m,n) , ans = -1;
		map<int,int> r = factor(n);
		for( map<int,int>::iterator it = r.begin() ; it != r.end() ; ++it){
			int a = it->first;
			int d = it->second;
			unsigned long long t = v;
			unsigned long long ok = 0;
			while(t){ ok += (t / a) ; t /= a;}
			ans = min(ok / d , ans);
		}
		cout << ans << endl;
	}
}
### Prompt

Develop a solution in cpp 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 <iostream>
#include <map>
#include <climits>
#include <string>
using namespace std;

unsigned long long to(string w , int base){
	unsigned long long ans = 0;
	for(int i = 0 ; i < w.size() ; i++) ans = ans * base + (w[i] >= 'A' ? w[i] - 'A' + 10 : w[i] - '0');
	return ans;
}

map<int,int> factor(int n){
	map<int,int> w;
	for(int i = 2 ; i*i<=n ; i++)
		while(n%i==0) w[i]++ , n /= i;
	if(n!=1) w[n]++;
	return w;
}

int main(){
	int n;
	string m;
	while(cin >> n >> m, n){
		unsigned long long v = to(m,n) , ans = -1;
		map<int,int> r = factor(n);
		for( map<int,int>::iterator it = r.begin() ; it != r.end() ; ++it){
			int a = it->first;
			int d = it->second;
			unsigned long long t = v;
			unsigned long long ok = 0;
			while(t){ ok += (t / a) ; t /= a;}
			ans = min(ok / d , ans);
		}
		cout << ans << endl;
	}
}
```