#include<fstream>
using namespace std;
long long v[1000001],p[1000001],a[101],i,j,tst,x,y,s,pr,d,k,t,m,sol,w;
int main()
{
	ifstream f("pinex.in");
	ofstream g("pinex.out");
	m=1000000;
	for(i=2;i<=m;i++)
		if(!v[i])
			for(p[++d]=i,j=i*i;j<=m;j+=i)
				v[j]=1;
	f>>tst;
	for(w=1;w<=tst;w++)
	{
		f>>x>>y;
		sol=x,k=0;
		for(i=1;i*i<=y;i++)
			if(y%p[i]==0)
				for(a[++k]=p[i];y%p[i]==0;y/=p[i]);
		if(y>1)
			a[++k]=y;
		for (t=1<<k,i=1;i<t;i++)
		{
			for(pr=1,s=j=0;j<k;j++)
				if((i&(1<<j))>0)
					s++,pr*=a[j+1];
			if (s%2==0)
				sol+=x/pr;
			else sol-=x/pr;
		}
		g<<sol<<"\n";
	}
}