#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
int d; char s[13];
int p[11] = { 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31 };
int main() {
	while (scanf("%d%s", &d, s), d) {
		long long v = 0;
		for (int i = 0; i < strlen(s); i++) v = v * d + (s[i] <= '9' ? s[i] - 48 : s[i] - 55);
		long long ret = 9191919191919191919;
		for (int i = 0; i < 11 && p[i] <= d; i++) {
			int e = 0, f = d;
			while (f % p[i] == 0) f /= p[i], e++;
			if (e) {
				long long w = v, x = 0;
				while (w) w /= p[i], x += w;
				ret = min(ret, x / e);
			}
		}
		printf("%lld\n", ret);
	}
}
### Prompt

Create a solution in CPP for 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 <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
int d; char s[13];
int p[11] = { 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31 };
int main() {
	while (scanf("%d%s", &d, s), d) {
		long long v = 0;
		for (int i = 0; i < strlen(s); i++) v = v * d + (s[i] <= '9' ? s[i] - 48 : s[i] - 55);
		long long ret = 9191919191919191919;
		for (int i = 0; i < 11 && p[i] <= d; i++) {
			int e = 0, f = d;
			while (f % p[i] == 0) f /= p[i], e++;
			if (e) {
				long long w = v, x = 0;
				while (w) w /= p[i], x += w;
				ret = min(ret, x / e);
			}
		}
		printf("%lld\n", ret);
	}
}
```