#include <stdio.h>
#include<string.h>
#include<stdlib.h>

#define MAX 65
#define INF 0x7fffffffffffffff

int  prime[20]={2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61};
int cnt=18;
int kv[20];

//求进制数k的素因子
void K_Prime( int k ){
int num,i;
memset( kv, 0, sizeof(kv) );
for( i=0; i<cnt; i++ ){
num = 0;
while( k%prime[i] == 0 ){
num++;
k = k/prime[i];
}
kv[i] = num;
}
}
//求阶乘n的末尾有多少个0
void jiecheng( long long sum,int k ){
long long i,num;
long long min = INF,tmp;
for(i=0; i<cnt; i++){
tmp = sum;
tmp /= prime[i];
num = tmp;
while( tmp ){
tmp /= prime[i];
num += tmp;
}
if( kv[i] && num/kv[i]<min )
min = num/kv[i];
}
printf( "%lld\n",min );
}
//把k进制数n转化为十进制数
long long char_int( char s[],int k ){
int len = strlen(s),i;
long long sum = 0;
for( i=0; i<len ; i++ ){
if( s[i]>='0' && s[i]<='9' )
sum = sum*k + (s[i]-'0');
else if( s[i]>='A' && s[i]<='Z' )
sum = sum*k + ( s[i]-'A' +10 );
else
sum = sum*k + ( s[i]-'a' + 36 );
}
return sum;
}

int main(){
char s[150];
int k;
long long sum;
while( scanf("%s%d", s, &k) != EOF ){
K_Prime(k);
sum = char_int( s,k );
jiecheng( sum,k );
}
return 0;
}