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
#include<iostream>
#include<string>
#include<cmath>
#include<algorithm>
using namespace std;
int N; string M;
int p[50]; long long power[20];
inline long long div(long long k, int m) {
	long long sum = 0;
	while (k >= 1) {
		k /= m; sum += k;
	}
	return sum;
}
int main() {
	while (true) {
		cin >> N >> M; power[0] = 1;
		for (int i = 0; i < 50; i++)p[i] = 0;
		for (int i = 1; i < M.size(); i++)power[i] = power[i - 1] * N;
		if (N == 0)break;
		long long C = 0;
		for (int i = 0; i < M.size(); i++) {
			int V = (char)(M[i] - '0'); if (M[i] >= 'A')V = (char)(M[i] - 'A') + 10;
			C += power[M.size() - 1 - i] * V;
		}
		int L = N;
		for (int i = 2; i <= L; i++) {
			while (L%i == 0) {
				L /= i; p[i]++;
			}
		}
		long long minx = 1LL << 62;
		for (int i = 2; i <= N; i++) {
			if (p[i] == 0)continue;
			minx = min(minx, div(C, i) / p[i]);
		}
		cout << minx << endl;
	}
	return 0;
}