#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,su,zz;
	int q;zz=0;
	eb=0;while(b%p==0){eb++;b/=p;}
	en=0;
	q=p;
	while(q<=n||q<0)
	{
		pt=(long long) n-q+1;
		nt=(long long)n/q;
		ra=(long long)-q;
		su=nt*(2*pt+(nt-1)*ra)/2;
		en+=su;zz+=en/eb;en%=eb;
		q*=p;
	}
	zsol=zsol<zz?zsol:zz;
}