#include <stdio.h>

void solve()
{
	int n,p,b,exp;

	scanf("%d %d",&n,&b);

	for (int i=2;i*i<=b;i++)
		if (b%i==0)
			for (p=i,exp=0;b%i==0;b/=i) exp++;
	if (b>1) {exp=1;p=b;}
	fprintf(stderr,"x");
	long long sol,x,e,ret=0;

	for (sol=0,x=p,e=1;x<=n;x*=p,e++) 
			{
				sol=sol+(n-x+1)*e;
				ret=ret+sol/exp;
				sol%=exp;
			}

	printf("%lld\n",ret);
}

int main()
{
	freopen("zero2.in","r",stdin);
	freopen("zero2.out","w",stdout);

	for (int i=1;i<=10;i++)
		solve();
	return 0;
}