#include<iostream>
#include<cmath>
#include<algorithm>
#include<vector>
#include<map>
#include<set>
#include<cassert>
#include<climits>

#define IINF (INT_MAX)
#define ULLINF (ULLONG_MAX)

using namespace std;

typedef unsigned long long ull;
typedef pair<ull,ull> ull2;

ull N;
string M;

map<ull,int> prime_factor(ull n){
  map<ull,int> res;
  for(int i=2;i*i<=n;i++){
    while(n % i == 0){
      ++res[i];
      n /= i;
    }
  }
  if(n != 1ULL)res[n] = 1ULL;
  return res;
}

ull StoULL(){
  ull ret = 0;
  for(int i=0;i<M.size();i++){
    ret *= N;
    ull tmp = (('0'<=M[i]&&M[i]<='9')?(M[i]-'0'):(M[i]-'A')+10ULL);
    ret += tmp;
  }
  return ret;
}

ull calc(ull value,ull2 tmp){
  ull ret = 0;
  ull pf = tmp.first;
  ull denom = tmp.second;
  while(value){
    ret += value / pf;
    value /= pf;
  }
  return ret/denom;
}

void compute(){
  map<ull,int> ppf = prime_factor(N);
  vector<ull2> pf;

  for(map<ull,int>::iterator it = ppf.begin() ; it != ppf.end() ; it++ ){
    pf.push_back(ull2((it->first),(it->second)));
  }

  ull value = StoULL();
  //cout << "value = " << value << endl;
  ull ans = ULLINF;

  for(int i=0;i<pf.size();i++){
    ans = min(ans,calc(value,pf[i]));
  }

  cout << ans << endl;

}

int main(){
  //cout << ULLINF << endl;
  while(cin >> N >> M,(N!=0 || M!="0")){

    compute();

  }
  return 0;
}
### Prompt

Please provide a cpp coded solution to the problem described below:

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<cmath>
#include<algorithm>
#include<vector>
#include<map>
#include<set>
#include<cassert>
#include<climits>

#define IINF (INT_MAX)
#define ULLINF (ULLONG_MAX)

using namespace std;

typedef unsigned long long ull;
typedef pair<ull,ull> ull2;

ull N;
string M;

map<ull,int> prime_factor(ull n){
  map<ull,int> res;
  for(int i=2;i*i<=n;i++){
    while(n % i == 0){
      ++res[i];
      n /= i;
    }
  }
  if(n != 1ULL)res[n] = 1ULL;
  return res;
}

ull StoULL(){
  ull ret = 0;
  for(int i=0;i<M.size();i++){
    ret *= N;
    ull tmp = (('0'<=M[i]&&M[i]<='9')?(M[i]-'0'):(M[i]-'A')+10ULL);
    ret += tmp;
  }
  return ret;
}

ull calc(ull value,ull2 tmp){
  ull ret = 0;
  ull pf = tmp.first;
  ull denom = tmp.second;
  while(value){
    ret += value / pf;
    value /= pf;
  }
  return ret/denom;
}

void compute(){
  map<ull,int> ppf = prime_factor(N);
  vector<ull2> pf;

  for(map<ull,int>::iterator it = ppf.begin() ; it != ppf.end() ; it++ ){
    pf.push_back(ull2((it->first),(it->second)));
  }

  ull value = StoULL();
  //cout << "value = " << value << endl;
  ull ans = ULLINF;

  for(int i=0;i<pf.size();i++){
    ans = min(ans,calc(value,pf[i]));
  }

  cout << ans << endl;

}

int main(){
  //cout << ULLINF << endl;
  while(cin >> N >> M,(N!=0 || M!="0")){

    compute();

  }
  return 0;
}
```