# include <iostream># include <cstdio># include <cstring>using namespace std;const int P[] = {2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61};const int PN = 18;long long s; int k;long long fact(long long s,int k){long long res = 0;while ( s > 0 ) res += (s/=k);return res;}int getNum(char c){if ( isdigit(c) ) return c - '0';if ( 'A' <= c && c <= 'Z') return 10 + c - 'A';return 36 + c - 'a';}bool getInit(){char a[100]; if ( scanf("%s",a) == EOF )return false;s = 0; scanf("%d", &k);for(int i=0; i<strlen(a); i++)s = s * k + getNum(a[i]);return true;}int main(){while ( getInit() ) {long long Ans = ~0ULL>>1;for(int i=0; i<PN; i++) {int t = 0;while( k % P[i] == 0 ) k /= P[i], t ++;if ( !t ) continue;Ans = min(Ans, fact(s,P[i]) / t);}cout << Ans << endl;}return 0;}
