#include <iostream>
#include <map>
#include <climits>
using namespace std;

unsigned long long to(string w , int base){
	unsigned long long ans = 0;
	for(int i = 0 ; i < w.size() ; i++) ans = ans * base + (w[i] >= 'A' ? w[i] - 'A' + 10 : w[i] - '0');
	return ans;
}

map<int,int> factor(int n){
	map<int,int> w;
	for(int i = 2 ; i*i<=n ; i++)
		while(n%i==0) w[i]++ , n /= i;
	if(n!=1) w[n]++;
	return w;
}
int main(){
	int n;
	string m;
	while(cin >> n >> m && (n||m!="0") ){
		unsigned long long v = to(m,n) , ans = ULLONG_MAX;
		map<int,int> r = factor(n);
		for( map<int,int>::iterator it = r.begin() ; it != r.end() ; ++it){
			int a = it->first;
			int d = it->second;
			unsigned long long t = v;
			unsigned long long ok = 0;
			while(t){ ok += (t / a) ; t /= a;}
			ans = min(ok / d , ans);
		}
		cout << ans << endl;
	}
}