#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <iostream>
#include <math.h>
#include <assert.h>
#include <vector>
#include <string>

using namespace std;
typedef long long ll;
typedef unsigned int uint;
typedef unsigned long long ull;
static const double EPS = 1e-9;
static const double PI = acos(-1.0);

#define REP(i, n) for (int i = 0; i < (int)(n); i++)
#define FOR(i, s, n) for (int i = (s); i < (int)(n); i++)
#define FOREQ(i, s, n) for (int i = (s); i <= (int)(n); i++)
#define FORIT(it, c) for (__typeof((c).begin())it = (c).begin(); it != (c).end(); it++)
#define MEMSET(v, h) memset((v), h, sizeof(v))

vector<pair<int, int> > PrimeFactor(int n) {
  vector<pair<int, int> > ret;
  FOREQ(i, 2, n) {
    int cnt = 0;
    while (n % i == 0) {
      n /= i;
      cnt++;
    }
    if (cnt != 0) {
      ret.push_back(make_pair(i, cnt));
    }
  }
  return ret;
}

ll calc(ll m, ll v) {
  if (m < v) { return 0; }
  return m / v + calc(m / v, v);
}

ll convert(string s, ll base) {
  ll ret = 0;
  FORIT(it, s) {
    ll v = 0;
    if (isdigit(*it)) { v = *it - '0'; }
    else { v = *it - 'A' + 10; }
    ret = ret * base + v;
  }
  return ret;
}

ll n;
string str;
int main() {
  while (cin >> n >> str, n) {
    ll m = convert(str, n);
    vector<pair<int, int> > factor = PrimeFactor(n);
    ll ans = 1LL << 62;
    FORIT(it, factor) {
      ans = min(ans, calc(m, it->first) / it->second);
    }
    printf("%lld\n", ans);
  }
}