#include <iostream>
#include <vector>
#include <cstdlib>
#include <climits>
using namespace std;

typedef unsigned long long ll;

int main(void){
	int N;
	string M;

	while(cin>>N>>M, N){
		ll m = strtoll(&M[0],NULL,N);
		int n = N;
		vector<int> v,s;

		for(int i=2;i<=n;i++){
			if(n % i != 0) continue;

			v.push_back(i);
			s.push_back(0);
			while(n % i == 0){
				s[v.size()-1]++;
				n /= i;
			}
		}

		ll ans = ULLONG_MAX;
		for(int i=0;i<v.size();i++){
			ll tmp = m;
			ll zero = 0;
			while(tmp /= v[i]) zero += tmp;
			ans = min(ans,zero/s[i]);
		}

		cout<<ans<<endl;
	}

	return 0;
}
### Prompt

Your task is to create 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 <vector>
#include <cstdlib>
#include <climits>
using namespace std;

typedef unsigned long long ll;

int main(void){
	int N;
	string M;

	while(cin>>N>>M, N){
		ll m = strtoll(&M[0],NULL,N);
		int n = N;
		vector<int> v,s;

		for(int i=2;i<=n;i++){
			if(n % i != 0) continue;

			v.push_back(i);
			s.push_back(0);
			while(n % i == 0){
				s[v.size()-1]++;
				n /= i;
			}
		}

		ll ans = ULLONG_MAX;
		for(int i=0;i<v.size();i++){
			ll tmp = m;
			ll zero = 0;
			while(tmp /= v[i]) zero += tmp;
			ans = min(ans,zero/s[i]);
		}

		cout<<ans<<endl;
	}

	return 0;
}
```