#include<cstdio>
#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
using namespace std;
#define REP(i,b,n) for(int i=b;i<n;i++)
#define rep(i,n)   REP(i,0,n)
#define ALL(C)     (C).begin(),(C).end()
#define pb         push_back
#define mp         make_pair
typedef long long ll;

ll mypow(ll n,ll a){
  if (n == 0)return 1;
  ll ret = mypow(n/2,a);
  ret=ret*ret;
  if (n%2 == 1)ret*=a;
  return ret;
}

ll val[255];
//div=27 46 -> 27 47
ll compute(string &a,ll div,int base){
  ll nowbase=mypow((int)a.size()-1,base);
  ll ret=0;
  ll rem=0;
  for(int i=0;i<a.size();i++){
    ret+=(rem+val[a[i]]*nowbase)/div;
    rem =(rem+val[a[i]]*nowbase)%div;
    nowbase/=base;
  }
  return ret;
}

void fact(int n,int *base,int *basenum,int &p){
  for(int i=2;i<=n;i++){
    if (n%i == 0){
      base[p]=i;
      basenum[p]=0;
      while(true){
	if (n/i == 0 || n%i != 0)break;
	n/=i;
	basenum[p]++;
      }
      p++;
    }
  }
}

ll count(int p,int *basenum,ll *cnt){
  ll ret=(1LL<<62);
  rep(i,p){
    ret=min(ret,cnt[i]/basenum[i]);
  }
  return ret;
}

int main(){
  //  check();
  for(int i=0;i<10;i++){
    val['0'+i]=i;
  }
  for(int i='A';i<='Z';i++){
    val[i]=i-'A' + 10;
  }

  int base[100];
  int basenum[100];
  ll cnt[100];
  int num[100];
  int in;
  string inp;
  while(cin>>in>>inp && in){
    int p=0;
    fact(in,base,basenum,p);

    rep(i,p){
      ll now=base[i];
      cnt[i]=0;
      while(true){
	ll tmp = compute(inp,now,in);
	if (tmp == 0)break;
	cnt[i]+=tmp;
	now*=base[i];
      }
    }
    cout << count(p,basenum,cnt) << endl;

  }
  return false;
}
### 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<cstdio>
#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
using namespace std;
#define REP(i,b,n) for(int i=b;i<n;i++)
#define rep(i,n)   REP(i,0,n)
#define ALL(C)     (C).begin(),(C).end()
#define pb         push_back
#define mp         make_pair
typedef long long ll;

ll mypow(ll n,ll a){
  if (n == 0)return 1;
  ll ret = mypow(n/2,a);
  ret=ret*ret;
  if (n%2 == 1)ret*=a;
  return ret;
}

ll val[255];
//div=27 46 -> 27 47
ll compute(string &a,ll div,int base){
  ll nowbase=mypow((int)a.size()-1,base);
  ll ret=0;
  ll rem=0;
  for(int i=0;i<a.size();i++){
    ret+=(rem+val[a[i]]*nowbase)/div;
    rem =(rem+val[a[i]]*nowbase)%div;
    nowbase/=base;
  }
  return ret;
}

void fact(int n,int *base,int *basenum,int &p){
  for(int i=2;i<=n;i++){
    if (n%i == 0){
      base[p]=i;
      basenum[p]=0;
      while(true){
	if (n/i == 0 || n%i != 0)break;
	n/=i;
	basenum[p]++;
      }
      p++;
    }
  }
}

ll count(int p,int *basenum,ll *cnt){
  ll ret=(1LL<<62);
  rep(i,p){
    ret=min(ret,cnt[i]/basenum[i]);
  }
  return ret;
}

int main(){
  //  check();
  for(int i=0;i<10;i++){
    val['0'+i]=i;
  }
  for(int i='A';i<='Z';i++){
    val[i]=i-'A' + 10;
  }

  int base[100];
  int basenum[100];
  ll cnt[100];
  int num[100];
  int in;
  string inp;
  while(cin>>in>>inp && in){
    int p=0;
    fact(in,base,basenum,p);

    rep(i,p){
      ll now=base[i];
      cnt[i]=0;
      while(true){
	ll tmp = compute(inp,now,in);
	if (tmp == 0)break;
	cnt[i]+=tmp;
	now*=base[i];
      }
    }
    cout << count(p,basenum,cnt) << endl;

  }
  return false;
}
```