#include <iostream>
#include <vector>
#include <map>
#include <string>

using namespace std;
typedef long long ll;

int PRIMES_COUNT = 11;
int PRIMES[] = { 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31 };

int main(){
	while(true){
		int base;
		string digits;
		cin >> base >> digits;
		if(base == 0){ break; }
		ll w = 1ll, input = 0;
		for(int i = digits.size() - 1; i >= 0; --i, w *= base){
			if('0' <= digits[i] && digits[i] <= '9'){
				input += (digits[i] - '0') * w;
			}else{
				input += (digits[i] - 'A' + 10) * w;
			}
		}
		vector<ll> counts(PRIMES_COUNT, 0);
		for(int i = 0; i < PRIMES_COUNT; ++i){
			ll tmp = input;
			while(tmp >= PRIMES[i]){
				tmp /= PRIMES[i];
				counts[i] += tmp;
			}
		}
		ll result = 0x7fffffffffffffffll;
		for(int i = 0; i < PRIMES_COUNT; ++i){
			int tmp = base, div = 0;
			while(tmp % PRIMES[i] == 0){
				tmp /= PRIMES[i];
				++div;
			}
			if(div != 0){ result = min(result, counts[i] / div); }
		}
		cout << result << endl;
	}
	return 0;
}
### Prompt

In cpp, your task is to solve 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 <vector>
#include <map>
#include <string>

using namespace std;
typedef long long ll;

int PRIMES_COUNT = 11;
int PRIMES[] = { 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31 };

int main(){
	while(true){
		int base;
		string digits;
		cin >> base >> digits;
		if(base == 0){ break; }
		ll w = 1ll, input = 0;
		for(int i = digits.size() - 1; i >= 0; --i, w *= base){
			if('0' <= digits[i] && digits[i] <= '9'){
				input += (digits[i] - '0') * w;
			}else{
				input += (digits[i] - 'A' + 10) * w;
			}
		}
		vector<ll> counts(PRIMES_COUNT, 0);
		for(int i = 0; i < PRIMES_COUNT; ++i){
			ll tmp = input;
			while(tmp >= PRIMES[i]){
				tmp /= PRIMES[i];
				counts[i] += tmp;
			}
		}
		ll result = 0x7fffffffffffffffll;
		for(int i = 0; i < PRIMES_COUNT; ++i){
			int tmp = base, div = 0;
			while(tmp % PRIMES[i] == 0){
				tmp /= PRIMES[i];
				++div;
			}
			if(div != 0){ result = min(result, counts[i] / div); }
		}
		cout << result << endl;
	}
	return 0;
}
```