#include<iostream>
#include<algorithm>
#include<vector>
#include<stack>
#include<map>
#include<set>
#include<queue>
#include<cstdio>
#include<climits>
#include<cmath>
#include<cstring>
#include<string>
#include<sstream>
#include<numeric>
#include<cassert>

#define f first
#define s second
#define mp make_pair

#define REP(i,n) for(int i=0; i<(int)(n); i++)
#define rep(i,s,n) for(int i=(s); i<(int)(n); i++)
#define FOR(i,c) for(__typeof((c).begin()) i=(c).begin(); i!=(c).end(); i++)
#define ALL(c) (c).begin(), (c).end()
#define IN(x,s,g) ((x) >= (s) && (x) < (g))
#define ISIN(x,y,w,h) (IN((x),0,(w)) && IN((y),0,(h)))
#define print(x) printf("%d\n",x)

using namespace std;

typedef unsigned int uint;
typedef unsigned long long ll;

const int _dx[] = {0,1,0,-1};
const int _dy[] = {-1,0,1,0};

int getInt(){
  int ret = 0,c;
  c = getchar();
  while(!isdigit(c)) c = getchar();
  while(isdigit(c)){
    ret *= 10;
    ret += c - '0';
    c = getchar();
  }
  return ret;
}

inline int toInt(char c){
  if(isdigit(c)) return c - '0';
  return c - 'A' + 10;
}

ll decode(char *num, int base){
  ll ret = 0;
  while(*num){
    ret *= base;
    ret += toInt(*num++);
  }
  return ret;
}

int main(){
  int base;
  char num[32];

  while(scanf("%d%s",&base,num),base){
    ll dec = decode(num, base);
    ll ans = (1ll)<<63;

    for(int d = 2; ; d++){
      if(base % d == 0){
        int cnt = 0;
        while(base % d == 0){
          base /= d;
          cnt++;
        }

        ll tmp = dec;
        ll a = 0;
        while(tmp){
          tmp /= d;
          a += tmp;
        }
        ans = min(ans, a/cnt);
        //printf("dec:%llu d:%d cnt:%d base:%d a:%llu\n",dec,d,cnt,base,a);
      }

      if(base == 1) break;
    }

    printf("%llu\n",ans);
  }

  return 0;
}
### Prompt

Develop a solution in Cpp 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<algorithm>
#include<vector>
#include<stack>
#include<map>
#include<set>
#include<queue>
#include<cstdio>
#include<climits>
#include<cmath>
#include<cstring>
#include<string>
#include<sstream>
#include<numeric>
#include<cassert>

#define f first
#define s second
#define mp make_pair

#define REP(i,n) for(int i=0; i<(int)(n); i++)
#define rep(i,s,n) for(int i=(s); i<(int)(n); i++)
#define FOR(i,c) for(__typeof((c).begin()) i=(c).begin(); i!=(c).end(); i++)
#define ALL(c) (c).begin(), (c).end()
#define IN(x,s,g) ((x) >= (s) && (x) < (g))
#define ISIN(x,y,w,h) (IN((x),0,(w)) && IN((y),0,(h)))
#define print(x) printf("%d\n",x)

using namespace std;

typedef unsigned int uint;
typedef unsigned long long ll;

const int _dx[] = {0,1,0,-1};
const int _dy[] = {-1,0,1,0};

int getInt(){
  int ret = 0,c;
  c = getchar();
  while(!isdigit(c)) c = getchar();
  while(isdigit(c)){
    ret *= 10;
    ret += c - '0';
    c = getchar();
  }
  return ret;
}

inline int toInt(char c){
  if(isdigit(c)) return c - '0';
  return c - 'A' + 10;
}

ll decode(char *num, int base){
  ll ret = 0;
  while(*num){
    ret *= base;
    ret += toInt(*num++);
  }
  return ret;
}

int main(){
  int base;
  char num[32];

  while(scanf("%d%s",&base,num),base){
    ll dec = decode(num, base);
    ll ans = (1ll)<<63;

    for(int d = 2; ; d++){
      if(base % d == 0){
        int cnt = 0;
        while(base % d == 0){
          base /= d;
          cnt++;
        }

        ll tmp = dec;
        ll a = 0;
        while(tmp){
          tmp /= d;
          a += tmp;
        }
        ans = min(ans, a/cnt);
        //printf("dec:%llu d:%d cnt:%d base:%d a:%llu\n",dec,d,cnt,base,a);
      }

      if(base == 1) break;
    }

    printf("%llu\n",ans);
  }

  return 0;
}
```