#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;

int main()
{
	ifstream f("pinex.in");
	ofstream g("pinex.out");
	m=1000000;
	for (i=2;i<=m;i++)
		if (v[i]==0)
		{
			p[++d]=i;
			for (j=i*i;j<=m;j+=i)
				v[j]=1;
		}	
	f >> tst;
	for (int w=1;w<=tst;w++)
	{
		f >> x >> y;
		sol=x;
		k=0;
		for (i=1;i*i<=y;i++)
			if (y%p[i]==0)
			{
				a[++k]=p[i];
				while (y%p[i]==0)
					y/=p[i];
			}
		if (y>1)
			a[++k]=y;
		t=1 << k;
		for (i=1;i<t;i++)
		{
			pr=1;s=0;
			for (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";
	}
	return 0;
}