#include<cstdio>
using namespace std;
long long n, b;
long long Nrp(long long n,long long p)
{
	long long k = n / (long long)p-1;
	return (k*(k + 1) / 2 * p + (k + 1)*(n - (k + 1)*p + 1));
}
int main()
{
	FILE *f, *g;
	f=fopen("zero2.in","r");
	g=fopen("zero2.out","w");
	long long min,d,factori[100], putere[100], nrf, p;
	int i,j;
	for (i = 1; i <= 10; ++i)
	{
		fscanf(f, "%Ld%Ld\n", &n, &b);
		d = 2; p = 0;
		nrf = 0;
		min = 1LL << 62;
		while (b > 1)
		{
			while (b%d == 0)
			{
				b = b / d;
				++p;
			}
			if (p > 0)
			{
				factori[++nrf] = d;
				putere[nrf] = p;
				p = 0;
			}
			++d;
		}
		for (j = 1; j <= nrf; ++j)
		{
			p = factori[j];
			d = 0;
			while (p <= n)
			{
				d = d + Nrp(n, p);
				p = p*factori[j];
			}
			if (d / putere[j] < min) min = d / putere[j];
		}
		fprintf(g, "%Ld\n", min);
	}
	fclose(f);
	fclose(g);
	return 0;
}