#include<fstream.h>
int main()
{
unsigned long int n,b,i,j,a,p=1,z;
ifstream f("zero.in");
ofstream g("zero.out");
for(a=1;a<=10;a++)
	{
	f>>n>>b;
	p=1;
	for(i=1;i<=n;i++)
		{
		for(j=1;j<=i;j++)
			{
 			p=p*j;
			}
		}
	z=0;
	while(p!=0&&p%b==0)
		{
		z++;
		p=p/b;
		}
	g<<z<<'\n';
	}
return 0;
}