#include <bits/stdc++.h>
using namespace std;
#define F first
#define S second
typedef long long ll;
typedef pair<ll,ll> P;
 
vector<P> D(ll n) {
  vector<P> v;
  for(ll i=2; i*i<=n; i++) {
    P p=P(0,i);
    while(n%i==0) {
      n/=i;
      p.F++;
    }
    if(p.F) v.push_back(p);
  }
  if(n>1) v.push_back(P(1,n));
  return v;
}
 
ll N(char c) {
  if(isdigit(c)) return c-'0';
  return (c-'A')+10;
}
 
ll C(string s,ll n) {
  ll x=0,y=1;
  for(int i=s.size()-1; i>=0; i--) {
    x+=N(s[i])*y;
    y*=n;
  }
  return x;
}
 
int main() {
  ll n;
  string s;
  while(cin >> n >> s && n) {
    vector<P> v=D(n);
    ll m=C(s,n),ans=1LL<<62;
    for(int i=0; i<v.size(); i++) {
      P p=v[i];
      ll z=0,x=p.S;
      while(1) {
        z+=m/x;
        if(x*p.S>m||x*p.S/p.S!=x) break;
        x*=p.S;
      }
      ans=min(ans,z/p.F);
    }
    cout << ans << endl;
  }
  return 0;
}

### Prompt

Please create a solution in Cpp 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>
using namespace std;
#define F first
#define S second
typedef long long ll;
typedef pair<ll,ll> P;
 
vector<P> D(ll n) {
  vector<P> v;
  for(ll i=2; i*i<=n; i++) {
    P p=P(0,i);
    while(n%i==0) {
      n/=i;
      p.F++;
    }
    if(p.F) v.push_back(p);
  }
  if(n>1) v.push_back(P(1,n));
  return v;
}
 
ll N(char c) {
  if(isdigit(c)) return c-'0';
  return (c-'A')+10;
}
 
ll C(string s,ll n) {
  ll x=0,y=1;
  for(int i=s.size()-1; i>=0; i--) {
    x+=N(s[i])*y;
    y*=n;
  }
  return x;
}
 
int main() {
  ll n;
  string s;
  while(cin >> n >> s && n) {
    vector<P> v=D(n);
    ll m=C(s,n),ans=1LL<<62;
    for(int i=0; i<v.size(); i++) {
      P p=v[i];
      ll z=0,x=p.S;
      while(1) {
        z+=m/x;
        if(x*p.S>m||x*p.S/p.S!=x) break;
        x*=p.S;
      }
      ans=min(ans,z/p.F);
    }
    cout << ans << endl;
  }
  return 0;
}

```