#include <fstream>
using namespace std;
int i, j, nrf;
long long Nrp(long long n,long long p)
{
	long long k = n /p-1;
	return (k*(k + 1) / 2 * p + (k + 1)*(n - (k + 1)*p + 1));
}
int main()
{
	long long n, b;
	long long  d,minim, factori[1000], putere[1000], p;
	ifstream f("zero2.in");
	ofstream g("zero2.out");
	for (i = 1; i <= 10; ++i)
	{
		f >> n >> b;
		d = 2; p = 0;
		nrf = 0;
		minim = 1LL << 62;
		for (j = 2; j*j <= b; ++j)
		{
			if (b%j == 0)
			{
				factori[++nrf] = j;
				putere[nrf] = 0;
				while (b%j == 0)
				{
					b /= j;
					++putere[nrf];
				}
			}
		}
		if (b>1) {
			factori[++nrf] = b;
			putere[nrf] = 1;
		}
		for (j = 1; j <= nrf; ++j)
		{
			p = factori[j];
			d = 0;
			while (p <= n)
			{
				d += Nrp(n, p);
				p*=factori[j];
			}
			d /= putere[j];
			if (d < minim) minim = d;
		}
		g << minim << "\n";
	}
	f.close();
	g.close();
	return 0;
}