#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
ifstream in("zero2.in");
ofstream out("zero2.out");
int n, b;
void rez()
{
	int i,j,minim=999999,lacatimpart,ceva=0;
	vector<int> ras;
	vector<int> cate;
	vector<int> rasfinal;
	vector<int> catefinal;
	for (i = 2; i*i <= b; i++)
	{
		while (b%i == 0)
		{
			b /= i;
			ras.push_back(i);
			cate.push_back(0);
		}
	}
	if (b > 1){ ras.push_back(b); cate.push_back(0); }
	ras.push_back(-1);
	for (i = 0; i < ras.size()-1; i++)
	{
		ceva = ras[i];
		for (j = 1; n - ceva + 1>0; j++)
		{
			cate[i] += (n - ceva + 1)*j;
			ceva *= ras[i];
		}
	}
	for (i = 0; i < ras.size()-1;)
	{
		catefinal.push_back(cate[i]);
		rasfinal.push_back(ras[i]);
		lacatimpart = 1;
		for (j = i + 1; j < ras.size(); j++)
		{
			if (ras[j] != ras[i]){ i = j; break; }
			else
			{
				lacatimpart++;
			}
		}
		catefinal[catefinal.size() - 1] /= lacatimpart;
	}
	for (i = 0; i < rasfinal.size(); i++)
	{
		if (catefinal[i] < minim){ minim = catefinal[i]; }
	}
	out << minim << "\n";
}
int main()
{
	int i;
	for (i = 1; i <= 10; i++)
	{
		in >> n;
		in >> b;
		rez();
	}
}