#include<iostream>
#include<vector>
#include<string>
#include<algorithm>	
#include<map>
#include<set>
#include<utility>
#include<cmath>
#include<cstring>
#include<queue>
#include<cstdio>
#include<sstream>
#include<iomanip>
#define loop(i,a,b) for(long long i=a;i<b;i++) 
#define rep(i,a) loop(i,0,a)
#define pb push_back
#define mp make_pair
#define all(in) in.begin(),in.end()
#define shosu(x) fixed<<setprecision(x)
using namespace std;
//kaewasuretyuui
typedef unsigned long long ll;
typedef pair<int,int> pii;
typedef vector<ll> vi;
typedef vector<vi> vvi;
typedef vector<pii> vp;
typedef vector<vp> vvp;
typedef pair<int,pii> pip;
typedef vector<pip>vip;
const double PI=acos(-1);
const double EPS=1e-2;
const ll inf=1e19;
int main(){
	ll n;
	string s;
	while(cin>>n>>s,n){
		ll m=strtoll(&s[0],NULL,n);
		vi a,b;
		loop(i,2,n+1){
			if(n%i)continue;
			a.pb(i);
			b.pb(0);
			while(n%i==0)b[b.size()-1]++,n/=i;
		}
		ll out=inf;
		rep(i,a.size()){
			ll tmp=m;
			ll t=0;
			while(tmp){
				tmp/=a[i];
				t+=tmp;
			}
			out=min(out,t/b[i]);
		}
		cout<<out<<endl;
	}
}
### 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<iostream>
#include<vector>
#include<string>
#include<algorithm>	
#include<map>
#include<set>
#include<utility>
#include<cmath>
#include<cstring>
#include<queue>
#include<cstdio>
#include<sstream>
#include<iomanip>
#define loop(i,a,b) for(long long i=a;i<b;i++) 
#define rep(i,a) loop(i,0,a)
#define pb push_back
#define mp make_pair
#define all(in) in.begin(),in.end()
#define shosu(x) fixed<<setprecision(x)
using namespace std;
//kaewasuretyuui
typedef unsigned long long ll;
typedef pair<int,int> pii;
typedef vector<ll> vi;
typedef vector<vi> vvi;
typedef vector<pii> vp;
typedef vector<vp> vvp;
typedef pair<int,pii> pip;
typedef vector<pip>vip;
const double PI=acos(-1);
const double EPS=1e-2;
const ll inf=1e19;
int main(){
	ll n;
	string s;
	while(cin>>n>>s,n){
		ll m=strtoll(&s[0],NULL,n);
		vi a,b;
		loop(i,2,n+1){
			if(n%i)continue;
			a.pb(i);
			b.pb(0);
			while(n%i==0)b[b.size()-1]++,n/=i;
		}
		ll out=inf;
		rep(i,a.size()){
			ll tmp=m;
			ll t=0;
			while(tmp){
				tmp/=a[i];
				t+=tmp;
			}
			out=min(out,t/b[i]);
		}
		cout<<out<<endl;
	}
}
```