#include<fstream>
using namespace std;
long long  A,B,BC,S,P,n,p[1100000],i,j,np,d,D[100000];
void read(),solve(),ciur();
ifstream f("pinex.in");
ofstream g("pinex.out");
void solve()
{
	ciur();
	D[0]=1;
	for(;n;n--)
	{
		f>>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];
		g<<S<<'\n';
	}
}
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;
}
int main()
{
	f>>n;
	solve();
	return 0;
}