#include<stdio.h>
#include<string.h>
int main(){
  int i,j,n,m,a,d[50],min;
  char s[5000],c[]={"0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ"};
  while(scanf("%d %s",&n,s),n){
    j=n;
    for(i=0;i*i<n;i++){
      while(j%i==0){
	j/=i;
	d[i]++;
      }
    }
    for(i=strlen(s)-1;i>0;i--){
      m*=n;
      for(j=0;c[j]-s[i];j++);
      m+=j;
    }
    for(i=0;i*i<n;i++){
      if(d[i]==0)continue;
      a=0;
      for(j=i;j<n;j*=i)a+=m/j;
      a/=d[i];
      if(min>a)min=a;
    }
  
  printf("%d\n",a);
  }
  return 0;
}