#include<stdio.h>
long v[1000001];
long long n,b,div,i,putere_n,putere_baza,nr,o,ic,j,k,nsol,nb,found;
struct lol
{
	long long n,b,solutie;
};
lol sol[21];
int main()
{
	freopen ("zero2.in","rt",stdin);
	freopen ("zero2.out","wt",stdout);

	v[0]=v[1]=1;
	for (i=2;i<=1000000;i++)
	{
		if (!v[i])
			for (j=i+i;j<=1000000;j+=i) v[j]=1;
	}

	for (o=1;o<=10;o++)
	{
		scanf("%lld %lld",&n,&b);
		nb=b;
		found=0;
		for (k=1;k<=nsol&&!found;k++)
			if (sol[k].n==n && sol[k].b==b)
			{printf("%lld\n",sol[k].solutie),found=1;}
		if (!found)
		{
			div=b;
			for (i=b/2;i>=2;i--)
				if ((!v[i]) && b%i==0)
				{div=i;break;}

			putere_baza=0;
 			while (b%div==0) {b/=div;putere_baza++;}

			nr=0;
			putere_n=0;
			for (i=1;i<=n;i++)
			{
				if (i%div==0)
				{
					ic=i;
					while (ic%div==0)
					{
						ic/=div;
						nr++;
					}
				}
				putere_n+=nr;
			}
			if (putere_baza==0)
				printf("0\n"),sol[++nsol].n=n,sol[nsol].b=nb,sol[nsol].solutie=0;
			else
				printf("%lld\n",putere_n/putere_baza),sol[++nsol].n=n,sol[nsol].b=nb,sol[nsol].solutie=putere_n/putere_baza;
		}
	}	
	return 0;
}