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

const int N_MAX = 1024;
const unsigned long long INF = 20000000000000000LL;

unsigned long long fact[N_MAX], put[N_MAX], rez[N_MAX];

unsigned long long nrap(unsigned long long N, unsigned long long X)
{
	unsigned long long s = (((N / X) - 1) * (N / X)) / 2;
	return ( (s * X) + ((N / X) * (N % X + 1)));
}
	

int main()
{
	freopen("zero2.in", "r", stdin);
	freopen("zero2.out", "w", stdout);
	
	unsigned long long T, N, B, b, p, i, MIN;
	
	for (T = 1; T <= 10; T ++) {
		scanf("%llu %llu\n", &N, &B);
	
		memset(put, 0, sizeof(put));
		memset(fact, 0, sizeof(fact));
		memset(rez, 0, sizeof(rez));
		//descompun baza in factori
		b = B;
		for (i = 2; i * i <= B; i ++) {
			if (b % i == 0) {
				fact[++ fact[0]] = i;
				put[fact[0]] = 1;
				b /= i;
				
				while (b % i == 0) {
					put[fact[0]] ++;
					b /= i;
				}
			}
		}
		
		if (b != 1) {
			fact[++ fact[0]] = b;
			put[fact[0]] = 1;
		}
		
		for (i = 1; i <= fact[0]; i ++) {
			p = fact[i];
			while (p <= N) {
				rez[i] += nrap(N, p);
				p *= fact[i];
			}
		}
		
		MIN = INF;
		for (i = 1; i <= fact[0]; i ++) {
			rez[i] /= put[i];
			if (rez[i] < MIN) {
				MIN = rez[i];
			}
		}
		
		printf("%llu\n", MIN);
	}								
	
	return 0;
}