#include<string>
#include<iostream>

using namespace std;

typedef	unsigned long long	ull;

int main(){
	int f[128];
	for(int i='0';i<='9';i++)	f[i]=i-'0';
	for(int i='A';i<='Z';i++)	f[i]=i-'A'+10;

	int base;
	string s;
	for(;cin>>base>>s,base;){
		ull num=0;
		for(int i=0;i<s.length();i++)	num=num*base+f[s[i]];

		const int p[]={31,29,23,19,17,13,11,7,5,3,2};
		int pcnt[11]={};
		for(int b=base,i=0;b>1;){
			if(b%p[i]==0)	b/=p[i],pcnt[i]++;
			else	i++;
		}

		ull zcnt=1ULL<<63;
		for(int i=0;i<11;i++){
			if(pcnt[i]>0){
				ull num2=num,zcnt2=0;
				while(num2)	zcnt2+=num2/p[i],num2/=p[i];
				zcnt=min(zcnt,zcnt2/pcnt[i]);
			}
		}
		cout<<zcnt<<endl;
	}

	return 0;
}