#include <bits/stdc++.h>

#define _overload(_1,_2,_3,name,...) name
#define _rep(i,n) _range(i,0,n)
#define _range(i,a,b) for(int i=int(a);i<int(b);++i)
#define rep(...) _overload(__VA_ARGS__,_range,_rep,)(__VA_ARGS__)

#define _rrep(i,n) _rrange(i,n,0)
#define _rrange(i,a,b) for(int i=int(a)-1;i>=int(b);--i)
#define rrep(...) _overload(__VA_ARGS__,_rrange,_rrep,)(__VA_ARGS__)

#define _all(arg) begin(arg),end(arg)
#define uniq(arg) sort(_all(arg)),(arg).erase(unique(_all(arg)),end(arg))
#define getidx(ary,key) lower_bound(_all(ary),key)-begin(ary)
#define clr(a,b) memset((a),(b),sizeof(a))
#define bit(n) (1LL<<(n))

template<class T>bool chmax(T &a, const T &b) { return (a<b)?(a=b,1):0;}
template<class T>bool chmin(T &a, const T &b) { return (b<a)?(a=b,1):0;}

using namespace std;
using ll=long long;

ll convert(char c){
	if(isdigit(c))
		return c - '0';
	else
		return c -'A'+10;
}

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

int main(void){
	ll n;
	string m;
	while(cin >> n >> m,n){
		ll num[11]={0};		
		ll mten=0LL;

		for(auto &d:m) mten=n*mten+convert(d);
		rep(i,11){
			ll cur=prime[i];
			while(1){
				num[i]+=mten/cur;
				if(cur>mten/prime[i]) break;
				cur*=prime[i];
			}
		}
		ll ans=-1LL;
		rep(i,11){
			ll cur=n,coef=0LL;
			while(cur%prime[i]==0) cur/=prime[i],coef++;  
			if(coef==0) continue;
			if(ans==-1)
				ans=num[i]/coef;
			else
				chmin(ans,num[i]/coef);
		}
		cout << ans << endl;
	}
	return 0;
}
### Prompt

Your challenge is to write 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 <bits/stdc++.h>

#define _overload(_1,_2,_3,name,...) name
#define _rep(i,n) _range(i,0,n)
#define _range(i,a,b) for(int i=int(a);i<int(b);++i)
#define rep(...) _overload(__VA_ARGS__,_range,_rep,)(__VA_ARGS__)

#define _rrep(i,n) _rrange(i,n,0)
#define _rrange(i,a,b) for(int i=int(a)-1;i>=int(b);--i)
#define rrep(...) _overload(__VA_ARGS__,_rrange,_rrep,)(__VA_ARGS__)

#define _all(arg) begin(arg),end(arg)
#define uniq(arg) sort(_all(arg)),(arg).erase(unique(_all(arg)),end(arg))
#define getidx(ary,key) lower_bound(_all(ary),key)-begin(ary)
#define clr(a,b) memset((a),(b),sizeof(a))
#define bit(n) (1LL<<(n))

template<class T>bool chmax(T &a, const T &b) { return (a<b)?(a=b,1):0;}
template<class T>bool chmin(T &a, const T &b) { return (b<a)?(a=b,1):0;}

using namespace std;
using ll=long long;

ll convert(char c){
	if(isdigit(c))
		return c - '0';
	else
		return c -'A'+10;
}

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

int main(void){
	ll n;
	string m;
	while(cin >> n >> m,n){
		ll num[11]={0};		
		ll mten=0LL;

		for(auto &d:m) mten=n*mten+convert(d);
		rep(i,11){
			ll cur=prime[i];
			while(1){
				num[i]+=mten/cur;
				if(cur>mten/prime[i]) break;
				cur*=prime[i];
			}
		}
		ll ans=-1LL;
		rep(i,11){
			ll cur=n,coef=0LL;
			while(cur%prime[i]==0) cur/=prime[i],coef++;  
			if(coef==0) continue;
			if(ans==-1)
				ans=num[i]/coef;
			else
				chmin(ans,num[i]/coef);
		}
		cout << ans << endl;
	}
	return 0;
}
```