#include<fstream>
#define LMax 1000010
#define NMax 1000
using namespace std;
ifstream fin("pinex.in");
ofstream fout("pinex.out");

typedef long long ll;


int Tes;
ll A,B,Rez;
int p[LMax] , pr[NMax];
bool b[LMax];

void ciur(){
	int i,j;
	for (i=2;i<LMax;++i) if (!b[i])
	{
		p[++p[0]]=i;
		if (i<=1000) for (j=i*i;j<LMax;j+=i)
			b[j]=true;
	}
}

void getpr(ll B){
	int i;
	for (i=1;1LL*p[i]*p[i]<=B && i<=p[0];++i)
	{
		if (B%p[i]==0)
		{
			pr[++pr[0]]=p[i];
			while (B%p[i]==0) B/=p[i];
		}
	}
	if (B!=1) pr[++pr[0]]=B;
}

int main()
{
	int mask,i,ct;
	ciur();
	
	fin>>Tes;
	
	while (Tes--)
	{
		fin>>A>>B;
		pr[0]=0;
		getpr(B);

		for (mask=1,ct=Rez=0;mask<(1<<pr[0]);++mask)
		{
			ll prod=1;ct=0;
			for (i=1;i<=pr[0];++i) if ((1<<i-1)&mask)
				prod*=pr[i],++ct;
			Rez+= (ct&1) ? A/prod : -A/prod;
		}
		fout<<A-Rez<<"\n";
	}
fin.close();
fout.close();
	return 0;
}