#include<stdio.h>
#define tip long long
tip A,B,BC,S,P,n,p[1100000],i,j,np,d,D[100000];
void read(),solve(),ciur();
int main()
{
	read();
	solve();
	return 0;
}
void read()
{
	freopen("pinex.in","r",stdin);
	freopen("pinex.out","w",stdout);
	scanf("%lld",&n);
}
void solve()
{
	ciur();
	D[0]=1;
	for(;n;n--)
	{
		scanf("%lld%lld",&A,&B);
		d=1;BC=B;
		for(i=1;i<=np;i++)
		{
			if(p[i]*p[i]>BC)break;
			if(BC%p[i]==0)
			{
				P=p[i];while(BC%P==0)BC/=P;P=-P;
				for(j=0;j<d;j++)D[j+d]=P*D[j];
				d*=2;				
			}
		}
		if(BC>1)
		{
			P=-BC;
			for(j=0;j<d;j++)D[j+d]=P*D[j];
			d*=2;
		}	
		S=0;
		for(i=0;i<d;i++)
			S+=A/D[i];
		printf("%lld\n",S);
	}
}
void ciur()
{
	for(i=2;i<=1000;i++)
		if(!p[i])
		{
			p[++np]=i;
			for(j=i*i;j<=1000000;j+=i)
				p[j]=1;
		}
	for(i=1001;i<=1000000;i++)
		if(!p[i])
			p[++np]=i;
}