#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<list>
#include<queue>
#include<deque>
#include<algorithm>
#include<numeric>
#include<utility>
#include<complex>
#include<functional>
 
using namespace std;

/* constant */

const int NUM_P = 11;
const int pnums[NUM_P] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31};

const unsigned long long LINF = ~1ULL;

/* typedef */

typedef pair<int,int> pii;
typedef unsigned long long ull;
typedef vector<pii> vpii;

/* global variables */

int n;
ull m;

/* subroutines */

inline int ch2int(char ch) {
  if (ch >= '0' && ch <= '9') return ch - '0';
  return ch - 'A' + 10;
}

void prime_decomp(int k, vpii& pds) {
  pds.clear();

  for (int pi = 0; k > 1; pi++) {
    int pn = pnums[pi];
    if (k % pn == 0) {
      int fi = 0;
      while (k % pn == 0)
	k /= pn, fi++;
      pds.push_back(pii(pn, fi));
    }
  }
}

void print_pds(vpii& pds) {
  for (int i = 0; i < pds.size(); i++) {
    if (i > 0) cout << '*';
    cout << pds[i].first << '^' << pds[i].second;
  }
  cout << endl;
}

/* main */

int main() {
  for (;;) {
    cin >> n;
    if (n == 0) break;

    string mstr;
    cin >> mstr;

    m = 0;
    for (int i = 0; i < mstr.length(); i++)
      m = m * n + ch2int(mstr[i]);
    //cout << m << endl;

    vpii pds;
    prime_decomp(n, pds);
    //print_pds(pds);

    ull min_numz = LINF;
    
    for (int i = 0; i < pds.size(); i++) {
      int pn = pds[i].first;
      ull pns = 0;
      for (ull pexp = pn; pexp <= m; pexp *= pn)
	pns += m / pexp;
      //printf("%lld: %d = %lld\n", m, pn, pns);

      ull numz = pns / pds[i].second;
      if (min_numz > numz) min_numz = numz;
    }

    cout << min_numz << endl;
  }

  return 0;
}
### Prompt

Generate 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<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<list>
#include<queue>
#include<deque>
#include<algorithm>
#include<numeric>
#include<utility>
#include<complex>
#include<functional>
 
using namespace std;

/* constant */

const int NUM_P = 11;
const int pnums[NUM_P] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31};

const unsigned long long LINF = ~1ULL;

/* typedef */

typedef pair<int,int> pii;
typedef unsigned long long ull;
typedef vector<pii> vpii;

/* global variables */

int n;
ull m;

/* subroutines */

inline int ch2int(char ch) {
  if (ch >= '0' && ch <= '9') return ch - '0';
  return ch - 'A' + 10;
}

void prime_decomp(int k, vpii& pds) {
  pds.clear();

  for (int pi = 0; k > 1; pi++) {
    int pn = pnums[pi];
    if (k % pn == 0) {
      int fi = 0;
      while (k % pn == 0)
	k /= pn, fi++;
      pds.push_back(pii(pn, fi));
    }
  }
}

void print_pds(vpii& pds) {
  for (int i = 0; i < pds.size(); i++) {
    if (i > 0) cout << '*';
    cout << pds[i].first << '^' << pds[i].second;
  }
  cout << endl;
}

/* main */

int main() {
  for (;;) {
    cin >> n;
    if (n == 0) break;

    string mstr;
    cin >> mstr;

    m = 0;
    for (int i = 0; i < mstr.length(); i++)
      m = m * n + ch2int(mstr[i]);
    //cout << m << endl;

    vpii pds;
    prime_decomp(n, pds);
    //print_pds(pds);

    ull min_numz = LINF;
    
    for (int i = 0; i < pds.size(); i++) {
      int pn = pds[i].first;
      ull pns = 0;
      for (ull pexp = pn; pexp <= m; pexp *= pn)
	pns += m / pexp;
      //printf("%lld: %d = %lld\n", m, pn, pns);

      ull numz = pns / pds[i].second;
      if (min_numz > numz) min_numz = numz;
    }

    cout << min_numz << endl;
  }

  return 0;
}
```