#include <iostream>
#include <sstream>
#include <string>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <cassert>
#include <climits>

using namespace std;

#define FOR(i,k,n) for(int i=(k); i<(int)n; ++i)
#define REP(i,n) FOR(i,0,n)
#define FORIT(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)

template<class T> void debug(T begin, T end){ for(T i = begin; i != end; ++i) cout<<*i<<" "; cout<<endl; }

typedef long long ll;
const ll INF = 1000000000000000000LL;
const double EPS = 1e-8;
const int MOD = 1000000007;

map<ll, ll> prime_factor(ll n){
	map<ll, ll> res;
	for(int i = 2; (ll)i * i <= n; i++){
		while(n % i == 0){
			++res[i];
			n /= i;
		}
	}
	if(n != 1) res[n] = 1;
	return res;
}
int main(){
	int N;
	string M;
	while(cin>>N>>M){
		if(N == 0 && M == "0")break;
		if(M == "0"){
			cout<<0<<endl;
			continue;
		}
		map<ll, ll> factor = prime_factor(N);
		map<ll, ll> cnt;
		ll L = strtoll(M.c_str(), NULL, N);
		if(L == 0) while(true);
		ll ans = LLONG_MAX;
		for(map<ll,ll>::iterator it = factor.begin(); it!=factor.end(); it++){
			for(ll i = it->first; i <= L ; i *= it->first){
				cnt[it->first] += L / i;
				if(L / i < it->first) break;
			}
			cnt[it->first] /= it->second;
			ans = min(cnt[it->first], ans);
		}
		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 <sstream>
#include <string>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <cassert>
#include <climits>

using namespace std;

#define FOR(i,k,n) for(int i=(k); i<(int)n; ++i)
#define REP(i,n) FOR(i,0,n)
#define FORIT(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)

template<class T> void debug(T begin, T end){ for(T i = begin; i != end; ++i) cout<<*i<<" "; cout<<endl; }

typedef long long ll;
const ll INF = 1000000000000000000LL;
const double EPS = 1e-8;
const int MOD = 1000000007;

map<ll, ll> prime_factor(ll n){
	map<ll, ll> res;
	for(int i = 2; (ll)i * i <= n; i++){
		while(n % i == 0){
			++res[i];
			n /= i;
		}
	}
	if(n != 1) res[n] = 1;
	return res;
}
int main(){
	int N;
	string M;
	while(cin>>N>>M){
		if(N == 0 && M == "0")break;
		if(M == "0"){
			cout<<0<<endl;
			continue;
		}
		map<ll, ll> factor = prime_factor(N);
		map<ll, ll> cnt;
		ll L = strtoll(M.c_str(), NULL, N);
		if(L == 0) while(true);
		ll ans = LLONG_MAX;
		for(map<ll,ll>::iterator it = factor.begin(); it!=factor.end(); it++){
			for(ll i = it->first; i <= L ; i *= it->first){
				cnt[it->first] += L / i;
				if(L / i < it->first) break;
			}
			cnt[it->first] /= it->second;
			ans = min(cnt[it->first], ans);
		}
		cout<<ans<<endl;
	}
	return 0;
}
```