#include<fstream.h>
#include<math.h>
int main()
{
unsigned long long int n,b,i,j,a,p=1,z,m,nr,x;
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++)
		{
		m=1;
		for(j=1;j<=i;j++)
			{
 			m=m*j;
			}
		p=p*m;
		}
	m=p;
	z=0;
	while(m!=0&&m%b==0)
		{
		z++;
		m=m/b;
		}
	g<<z<<'\n';
	}
return 0;
}