#include<bits/stdc++.h>
using namespace std;
using Int = long long;

template<typename T1,typename T2> void chmin(T1 &a,T2 b){if(a>b) a=b;};
template<typename T1,typename T2> void chmax(T1 &a,T2 b){if(a<b) a=b;};


signed main(){
  int n;
  string s;
  
  while(cin>>n>>s,n){
    using ull = unsigned long long;
    ull m=0;

    auto calc=[](char c){if(isdigit(c)) return c-'0';return c-'A'+10;};
  
    for(int i=0;i<(int)s.size();i++){
      m=m*n+calc(s[i]);
    }

    using P = pair<int, int>;
    vector<P> vp;
    int k=n;
    for(int i=2;i<=50;i++){
      if(k%i) continue;
      vp.emplace_back(i,0);
      while(k%i==0) k/=i,vp.back().second++;
    }
  
    ull ans=m;

    for(auto p:vp){
      ull k=p.first;
      ull res=0;
      while(k<=m){
	res+=m/k;
	if(k>=ULLONG_MAX/p.first-1) break;
	k*=p.first;
      }
      chmin(ans,res/p.second);
    }
  
    cout<<ans<<endl;
  }
  return 0;
}


### Prompt

In cpp, your task is to solve 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;
using Int = long long;

template<typename T1,typename T2> void chmin(T1 &a,T2 b){if(a>b) a=b;};
template<typename T1,typename T2> void chmax(T1 &a,T2 b){if(a<b) a=b;};


signed main(){
  int n;
  string s;
  
  while(cin>>n>>s,n){
    using ull = unsigned long long;
    ull m=0;

    auto calc=[](char c){if(isdigit(c)) return c-'0';return c-'A'+10;};
  
    for(int i=0;i<(int)s.size();i++){
      m=m*n+calc(s[i]);
    }

    using P = pair<int, int>;
    vector<P> vp;
    int k=n;
    for(int i=2;i<=50;i++){
      if(k%i) continue;
      vp.emplace_back(i,0);
      while(k%i==0) k/=i,vp.back().second++;
    }
  
    ull ans=m;

    for(auto p:vp){
      ull k=p.first;
      ull res=0;
      while(k<=m){
	res+=m/k;
	if(k>=ULLONG_MAX/p.first-1) break;
	k*=p.first;
      }
      chmin(ans,res/p.second);
    }
  
    cout<<ans<<endl;
  }
  return 0;
}


```