#include <iostream>
#include <string>
#include <map>
#define int long long
#define INF 4e+18
using namespace std;

signed main(){
	int n,tmp = 0;
	string m;
	while(cin >> n >> m,n){
	tmp = 0;
	for(int i = 0;i < m.length();i++){
		if('0' <= m[i] && m[i] <= '9'){
			tmp = tmp * n + m[i] - '0';
		}else {
			tmp = tmp * n + 10 + m[i] - 'A';
		}
	}
	map<int,int> insuu;
	for(int i = 2;i * i <= n;i++){
		while(n % i == 0) {
			insuu[i]++;
			n /= i;
		}
	}
	if(n != 1) insuu[n]++;
	int mi = INF;
	for(auto it = insuu.begin();it != insuu.end();it++){
		int t = tmp,cnt = 0;
		while(t){
			cnt += t / it->first;
			t /= it->first;
		}
		mi = min(mi,cnt / it->second);
	}
	cout << mi << endl;
	}
	return 0;
}
### Prompt

Generate 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>
#include <map>
#define int long long
#define INF 4e+18
using namespace std;

signed main(){
	int n,tmp = 0;
	string m;
	while(cin >> n >> m,n){
	tmp = 0;
	for(int i = 0;i < m.length();i++){
		if('0' <= m[i] && m[i] <= '9'){
			tmp = tmp * n + m[i] - '0';
		}else {
			tmp = tmp * n + 10 + m[i] - 'A';
		}
	}
	map<int,int> insuu;
	for(int i = 2;i * i <= n;i++){
		while(n % i == 0) {
			insuu[i]++;
			n /= i;
		}
	}
	if(n != 1) insuu[n]++;
	int mi = INF;
	for(auto it = insuu.begin();it != insuu.end();it++){
		int t = tmp,cnt = 0;
		while(t){
			cnt += t / it->first;
			t /= it->first;
		}
		mi = min(mi,cnt / it->second);
	}
	cout << mi << endl;
	}
	return 0;
}
```