#include <fstream>
using namespace std;
long long n, b;
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()
{
	ifstream f("zero2.in");
	ofstream g("zero2.out");
	long long factori[100],putere[100],nrf,p,d,min;
	int i,j;
	for (i = 1; i <= 10; ++i)
	{
		f >> 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];
		}
		g << min << "\n";
	}
	f.close();
	g.close();
	return 0;
}