#include <bits/stdc++.h>
#define int unsigned long long
#define r(i,n) for(int i=0;i<n;i++)
using namespace std;

 
typedef pair<int,int>P;
 
int sosu[]={2,3,5,7,11,13,17,19,23,29,31,37},so=12;
 
int con(int n,string s){
  int res=0;
  for(int i=0;i<s.size();i++){
 
    res*=n;
     
    if(isalpha(s[i])){
      res+=(s[i]-'A')+10;
    }
    else{
      res+=(s[i]-'0');
    }
 
  }
  return res;
}
 
vector<int> bunkai(int n){
  vector<int>v;
  r(i,so){
    while(n%sosu[i]==0){
      n/=sosu[i];
      v.push_back(sosu[i]);
    }
  }
  return v;
}
 
signed main(){
 int N;
  string s;
  while( cin>>N>>s , N ){
    int n=N;
    int p=con(n,s);//cout<<p<<endl;
 
    vector<int>v=bunkai(n);
     
    vector<P>vec,vel;
 
    r(i,v.size()){
      int res=0;
      __int128 x=1;
      if(i&&v[i-1]==v[i])continue;
      __int128 pp=p;
      for(int j=1;;j++){
     
        x*=v[i];
 
        if(x>pp)break;
     
        res+=p/x;
      }
      vec.push_back(P(res,v[i]));
    }
     
    r(i,so){
      int res=0;
      r(j,v.size()){
        if(sosu[i]==v[j])res++;
      }
      if(res==0)continue;
      //cout<<sosu[i]<<' '<<res<<endl;
      //cout<<p/sosu[i]<<endl;
      vel.push_back(P(res,sosu[i]));
    }
 
    unsigned long long ans=ULLONG_MAX;
    r(i,vec.size()){
      ans=min(ans,(unsigned long long)(vec[i].first/vel[i].first));
    }
 
    cout<<ans<<endl;
  }
}

### Prompt

Please formulate 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 int unsigned long long
#define r(i,n) for(int i=0;i<n;i++)
using namespace std;

 
typedef pair<int,int>P;
 
int sosu[]={2,3,5,7,11,13,17,19,23,29,31,37},so=12;
 
int con(int n,string s){
  int res=0;
  for(int i=0;i<s.size();i++){
 
    res*=n;
     
    if(isalpha(s[i])){
      res+=(s[i]-'A')+10;
    }
    else{
      res+=(s[i]-'0');
    }
 
  }
  return res;
}
 
vector<int> bunkai(int n){
  vector<int>v;
  r(i,so){
    while(n%sosu[i]==0){
      n/=sosu[i];
      v.push_back(sosu[i]);
    }
  }
  return v;
}
 
signed main(){
 int N;
  string s;
  while( cin>>N>>s , N ){
    int n=N;
    int p=con(n,s);//cout<<p<<endl;
 
    vector<int>v=bunkai(n);
     
    vector<P>vec,vel;
 
    r(i,v.size()){
      int res=0;
      __int128 x=1;
      if(i&&v[i-1]==v[i])continue;
      __int128 pp=p;
      for(int j=1;;j++){
     
        x*=v[i];
 
        if(x>pp)break;
     
        res+=p/x;
      }
      vec.push_back(P(res,v[i]));
    }
     
    r(i,so){
      int res=0;
      r(j,v.size()){
        if(sosu[i]==v[j])res++;
      }
      if(res==0)continue;
      //cout<<sosu[i]<<' '<<res<<endl;
      //cout<<p/sosu[i]<<endl;
      vel.push_back(P(res,sosu[i]));
    }
 
    unsigned long long ans=ULLONG_MAX;
    r(i,vec.size()){
      ans=min(ans,(unsigned long long)(vec[i].first/vel[i].first));
    }
 
    cout<<ans<<endl;
  }
}

```