#include<stdio.h>
long long enorm,zsol;
int t,n,b,p,k;
void readd(),solve(),solve_test(),act();
int main()
{
	readd();
	solve();
	return 0;
}
void readd()
{
	enorm=1;enorm<<=31;enorm<<=31;enorm<<=1;enorm--;
	freopen("zero2.in","r",stdin);
	freopen("zero2.out","w",stdout);
}
void solve()
{
	for(t=10;t;t--){scanf("%d%d",&n,&b);solve_test();}
}
void solve_test()
{
	zsol=enorm;
	p=2;if(b%p==0)act();
	p=3;if(b%p==0)act();
	for(k=6;;k+=6){p=k-1;if(p*p>b)break;if(b%p==0)act();p=k+1;if(p*p>b)break;if(b%p==0)act();}
	p=b;if(b>1)act();
	printf("%lld\n",zsol);
}
void act()
{
	long long eb,en,pt,nt,ra,zz,r1,r2,c1,c2,f1,f2,rr;
	int q;zz=0;
	eb=0;while(b%p==0){eb++;b/=p;}
	rr=0;
	q=p;
	while(q<=n||q<0)
	{
		pt=(long long) n-q+1;
		nt=(long long)n/q;
		ra=(long long)-q;
		f1=nt;
		f2=2*pt+(nt-1)*ra;
		if(f1%2)f2/=2;
		else f1/=2;
		c1=f1/eb;r1=f1%eb;
		c2=f2/eb;r2=f2%eb;
		zz+=c1*c2*eb+c1*r2+c2*r2;
		rr+=r1*r2;
		zz+=rr/eb;
		rr%=eb;
		q*=p;
	}
	zsol=zsol<zz?zsol:zz;
}