#include<iostream>
#include<vector>
#include<map>
#include<math.h>
#include<cassert>

const int MAX_P = 37;
using namespace std;

typedef unsigned long long ull;

vector<int> vprimes;
bool isPrime[MAX_P];

void MakePrime(){
  isPrime[0]=false;
  isPrime[1]=false;
  isPrime[2]=true;
  for(int i = 2; i < MAX_P; ++i){
    isPrime[i] = true;
  }
  for(int i = 2; i < MAX_P; ++i){
    if( isPrime[i] ){
      for(int j = 2; i * j < MAX_P; ++j) {
	isPrime[i*j] = false;
      }
    }
  }
  for(int i = 0; i < MAX_P; ++i){
    if( isPrime[i] ){
      vprimes.push_back( i );
    }
  }
}

ull convtodec(string t, ull B){
  ull ret = 0;
  for(int i = 0; i < (int)t.length(); ++i){
    int d = 0;
    if(t[i]>='A'&&t[i]<='Z')d=t[i]-'A'+10;
    else d=t[i]-'0';
    //cout << t[0] << ' ' << d << endl;
    ret *= B;
    ret += d;
  }
  return ret;
}

ull ipow(ull t, int p){
  ull ret = 1;
  for(int i = 0; i < p; ++i){
    ret *= t;
  }
  return ret;
}

int main(){
  MakePrime();
  ull N,B;
  ull base;
  string num;
  while(cin>>base>>num){
    if( base == 0 ) break;
    if( base == 0 && num[0] == '0' ) break;

    N = convtodec(num,base);
    B = base;

    //cout << N << ' ' << B << endl;

    ull num[vprimes.size()];
    for(int i = 0; i < (int)vprimes.size(); ++i){
      num[i] = 0;
      int maxpow = 1;
      while(N>=ipow(vprimes[i],maxpow)){
	++maxpow;
      }
      --maxpow;

      ull presum = 0;
      for(int p = maxpow; p >= 1; --p){
	ull tnum = (N / ipow(vprimes[i],p)) - presum;
	presum += tnum;
	num[i] += p * tnum;
      }
      //cout << vprimes[i] << ' ' << num[i] << endl;
    }

    ull res = 1LL<<62;
    for(int i = 0; i < (int)vprimes.size(); ++i){
      int e = 0;
      ull tB = B;
      while(tB % vprimes[i] == 0){
	++e;
	tB /= vprimes[i];
      }
      if( e > 0 ){
	res = min(res, num[ i ] / e);
      }
    }
    if( res == 1LL<<62 ) res = 0;

    cout << res << 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<iostream>
#include<vector>
#include<map>
#include<math.h>
#include<cassert>

const int MAX_P = 37;
using namespace std;

typedef unsigned long long ull;

vector<int> vprimes;
bool isPrime[MAX_P];

void MakePrime(){
  isPrime[0]=false;
  isPrime[1]=false;
  isPrime[2]=true;
  for(int i = 2; i < MAX_P; ++i){
    isPrime[i] = true;
  }
  for(int i = 2; i < MAX_P; ++i){
    if( isPrime[i] ){
      for(int j = 2; i * j < MAX_P; ++j) {
	isPrime[i*j] = false;
      }
    }
  }
  for(int i = 0; i < MAX_P; ++i){
    if( isPrime[i] ){
      vprimes.push_back( i );
    }
  }
}

ull convtodec(string t, ull B){
  ull ret = 0;
  for(int i = 0; i < (int)t.length(); ++i){
    int d = 0;
    if(t[i]>='A'&&t[i]<='Z')d=t[i]-'A'+10;
    else d=t[i]-'0';
    //cout << t[0] << ' ' << d << endl;
    ret *= B;
    ret += d;
  }
  return ret;
}

ull ipow(ull t, int p){
  ull ret = 1;
  for(int i = 0; i < p; ++i){
    ret *= t;
  }
  return ret;
}

int main(){
  MakePrime();
  ull N,B;
  ull base;
  string num;
  while(cin>>base>>num){
    if( base == 0 ) break;
    if( base == 0 && num[0] == '0' ) break;

    N = convtodec(num,base);
    B = base;

    //cout << N << ' ' << B << endl;

    ull num[vprimes.size()];
    for(int i = 0; i < (int)vprimes.size(); ++i){
      num[i] = 0;
      int maxpow = 1;
      while(N>=ipow(vprimes[i],maxpow)){
	++maxpow;
      }
      --maxpow;

      ull presum = 0;
      for(int p = maxpow; p >= 1; --p){
	ull tnum = (N / ipow(vprimes[i],p)) - presum;
	presum += tnum;
	num[i] += p * tnum;
      }
      //cout << vprimes[i] << ' ' << num[i] << endl;
    }

    ull res = 1LL<<62;
    for(int i = 0; i < (int)vprimes.size(); ++i){
      int e = 0;
      ull tB = B;
      while(tB % vprimes[i] == 0){
	++e;
	tB /= vprimes[i];
      }
      if( e > 0 ){
	res = min(res, num[ i ] / e);
      }
    }
    if( res == 1LL<<62 ) res = 0;

    cout << res << endl;
  }
  return 0;
}
```