#include<fstream>
using namespace std;
int T;
long long A,B,prime[100100],v[1000];
int nrp;
bool ciur[1000100];

inline void PrecalculareNrPrime()
{
	int i,j;
	prime[++nrp]=2;
	for(i=3;i<1000;i+=2)
	{
		if(ciur[i]==false)
		{
			prime[++nrp]=(long long)i;
			for(j=i*i;j<=1000000;j+=2*i)
				ciur[j]=true;
		}
	}
	for(i=1001;i<1000000;i+=2)
		if(ciur[i]==false)
			prime[++nrp]=(long long)i;
}

int main()
{
	int conf,lim,i,nrd;
	long long prod,semn,sol;
	ifstream fin("pinex.in");
	ofstream fout("pinex.out");
	PrecalculareNrPrime();
	fin>>T;
	while(T--)
	{
		fin>>A>>B;
		sol=A;
		nrd=0;
		i=1;
		while(i<=nrp && B>1LL)
		{
			if(B%prime[i]==0LL)
			{
				v[++nrd]=prime[i];
				while(B%prime[i]==0LL)
					B/=prime[i];
			}
			i++;
		}
		if(B>1LL)
			v[++nrd]=B;
		lim=(1<<nrd);
		for(conf=1;conf<lim;conf++)
		{
			semn=1LL;
			prod=1LL;
			for(i=0;i<nrd;i++)
			{
				if((conf&(1<<i))!=0)
				{
					semn=-semn;
					prod*=v[i+1];
				}
			}
			sol+=semn*(A/prod);
		}
		fout<<sol<<"\n";
	}
	fin.close();
	fout.close();
	return 0;
}