#include<stdio.h>
int t,n,i,b,k,p,pp,nf,f[20],e[20],best,sc,st;
void readd(),solve(),solve_test(),factb(),fact(int q),clean(),upd_best();
int main()
{
	readd();
	solve();
	return 0;
}
void readd()
{
	freopen("zero2.in","r",stdin);
	freopen("zero2.out","w",stdout);
}
void solve()
{
	for(t=10;t;t--){scanf("%d%d",&n,&b);solve_test();clean();}
}
void solve_test()
{
	factb();
	for(best=100,i=1;i<=nf;i++)upd_best();
	best=(best-100)?best:0;
	printf("%d\n",best);
}
void factb()
{
	nf=0;
	fact(2);
	fact(3);
	for(k=6;;k+=6)
	{ p=k-1;if(p*p>b)break;fact(p);
	  p=k+1;if(p*p>b)break;fact(p);
	}
	if(b>1){f[++nf]=b;e[nf]=1;}
}
void fact(int q)
{
	if(b%q)return;
	f[++nf]=q;
	while(!(b%q)){e[nf]++;b/=q;}
}
void clean()
{
	for(;nf;)e[nf--]=0;
}
void upd_best()
{
	st=0;p=f[nf];pp=p;
	do{k=n/pp-1;sc=k*(k+1)/2*pp+(k+1)*(n-(k+1)*pp+1);st+=sc;pp*=p;}while(sc);
	st/=e[nf];
	best=(best<st)?best:st;
}