#include <fstream>
#include <bitset>
#include <cmath>
using namespace std;
#define dim 1000005
#define ll long long
ifstream fin("pinex.in");
ofstream fout("pinex.out");
bitset <dim> v;
ll prime[dim/10],a,b;
int factor[dim/10], putere[dim/10];

void solve()
{
	int d=0, vf=0;
	while(b>1)
	{
		++d;
		if(b%prime[d]==0)
		{
			factor[++vf]=prime[d];
			while(b%prime[d]==0)
				b/=prime[d];
		}
		if(prime[d]*prime[d]>b && b>1)
		{
			factor[++vf]=b;
			b=1;
		}
	}
	
	ll sol=a;
	
	for(int i=1;i<(1<<vf);++i)
	{
		ll val=0;
		ll prod=1;
		for(int j=0;j<vf;++j)
			if( (1<<j)&i)
			{
				prod=1LL*prod*factor[j+1];
				++val;
			}
	
		if(val%2==1)
			val=-1;
		else
			val=1;
		
		sol=sol+1LL*val*a/prod;
	}
	fout<<sol <<'\n';
}

int main()
{
	int  i, nr=0,t;
	fin>>t;
	
	prime[++nr]=2;
	
	for(i=2;i<dim;++i)
	{
		++i;
		if(v[i]==0)
		{
			prime[++nr]=i;
			for(int j=1;j<dim/i;++j)
			{
				v[j*i]=1;
				++j;
			}
		}
	}
	
	for(;t;--t)
	{
		fin>>a >>b;
		solve();
	}
	
	return 0;
}