#include<stdio.h>
long long enorm,zsol,t,n,b,p,q,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("%lld%lld",&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 nt,st,eb,en,zz;
	en=0;
	eb=0;while(b%p==0){eb++;b/=p;}
	q=p;
	while(q<=n)
	{
		nt=n/q;
		st=2*n-(nt+1)*q+2;
		if(nt%2)st/=2;
			else nt/=2;
		en+=nt*st;
		q*=p;
	}
	zz=en/eb;
	zsol=zsol<zz?zsol:zz;
}