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