/*****************************************************************************
 *  !
 *
 *                      Written by T. Yoshino <tossy-2@yl.is.s.u-tokyo.ac.jp>
 *****************************************************************************/
#include <iostream>
#include <vector>
#include <string>
#include <cstdio>
#include <cstdlib>
using namespace std;

int main()
{
  int N;
  string Mstr;
  while(cin >> N >> Mstr, N) {
    assert(N >= 8 && N <= 36);
    long long M = strtoll(Mstr.c_str(), NULL, N);
    
    // Prime factorize N
    vector<pair<int, int> > component;
    for(int n = N, a = 2; a <= n; a++) {
      int c = 0;
      while(n % a == 0) n /= a, c++;
      if(c) component.push_back(make_pair(a, c)); // has a^c as a component
    }
    assert(component.size() >= 1);
    
    // Count the total number in the product of [1..M] for each component of N
    long long minval = LONG_LONG_MAX;
    for(int i = 0; i < component.size(); i++) {
      long long m = M, sum = 0LL;
      while(m) sum += m /= component[i].first;
      minval = min(minval, sum / component[i].second);
    }
    
    cout << minval << endl;
  }
}