#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,k,ret=0;

	for (sol=0,x=p;x<=n;x*=p) 
			{
				k=n/x;
				sol=sol+x*(k-1)*k /2 + k * (n%x+1);
				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;
}