#include <iostream>
#include <vector>
#include <cstdlib>
#include <climits>
using namespace std;

typedef unsigned long long ll;

int main(void){
	int N;
	string M;

	while(cin>>N>>M, N){
		ll m = strtoll(&M[0],NULL,N);
		int n = N;
		vector<int> v,s;

		for(int i=2;i<=n;i++){
			if(n % i != 0) continue;

			v.push_back(i);
			s.push_back(0);
			while(n % i == 0){
				s[v.size()-1]++;
				n /= i;
			}
		}

		ll ans = ULLONG_MAX;
		for(int i=0;i<v.size();i++){
			ll tmp = m;
			ll zero = 0;
			while(tmp /= v[i]) zero += tmp;
			ans = min(ans,zero/s[i]);
		}

		cout<<ans<<endl;
	}

	return 0;
}