#include<stdio.h>
long v[1000001];
long long n,b,div,i,putere_n,putere_baza,nr,o,ic,j;
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);
		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");
		else
			printf("%lld\n",putere_n/putere_baza);
	}	
	return 0;
}