#include <bits/stdc++.h>

using namespace std;

ifstream in("pinex.in");
ofstream out("pinex.out");

bool ciur[1000005];
int prime[100000],k=0;

long long factori[100001];
int main()
{
	for(int i=2;i<1000000;i++)
	{
		if(ciur[i]==false)
		{
			ciur[i]=true;
			prime[++k]=i;
			for(int j=i+i;j<1000000;j++)
				ciur[j]=true;
		}
	}
	long long n;
	in>>n;
	for(int i=1;i<=n;i++)
	{
		long long a,b,ct=0,cnt=0;
		in>>a>>b;
		long long sol=a;
		while(b>1)
		{
			ct++;
			if(b%prime[ct]==0)
			{
				factori[++cnt]=prime[ct];
				while(b%prime[ct]==0)
					b/=prime[ct];
			}
			if(prime[ct]>sqrt(b) && b>1)
			{
				factori[++cnt]=b;
				b=1;
			}
		}
		for(int i=1;i<(1<<cnt);i++)
		{
			long long howMany=0,produs=1;
			for(int j=0;j<cnt;j++)
			{
				if((1<<j)&i)
				{
					howMany++;
					produs=1ll*produs*factori[j+1];
				}
			}
				if(howMany%2==0) howMany=1;
				else howMany=-1;

				sol=sol+1ll*howMany*a/produs;
		}
		out<<sol<<"\n";
	}
	return 0;
}