#include <stdio.h>

#define LL unsigned long long

int N, B;

int pr[50];
int nr[50];

LL get_nr(int x, int N)
{
	int q, r;
	LL rez = 0;
	LL aux = x;
	
	for (; aux <= N; aux *= x) {
		q = N / aux;
		r = N % aux;
		rez += (LL) (q-1) * (q) / 2 * aux + (LL) q * (r + 1);
	}
	
return rez;
}

int main()
{
	int T, i;
	LL jeg;
	
    freopen("zero2.in", "r", stdin);
    freopen("zero2.out", "w", stdout);
    
    for (T = 1; T <= 10; T++) {
        scanf("%d %d", &N, &B);

        pr[0] = 0;
        for (i = 2; i * i <= B; i++) {
            if (B % i == 0) pr[++pr[0]] = i, nr[pr[0]] = 0;
            while (B % i == 0) {
                  B /= i;
                  nr[pr[0]]++;
            }
        }
        if (B > 1) pr[++pr[0]] = B, nr[pr[0]] = 1;
        
        LL rez = ((LL) 1 << 62);
        
        for (i = 1; i <= pr[0]; i++) {
            jeg = get_nr(pr[i], N);
            if (jeg / nr[i] < rez) rez = jeg / nr[i];
        }
        
        printf("%llu\n", rez);
    }
    
fclose(stdin);
fclose(stdout);
return 0;
}