#include <bits/stdc++.h>
#define pb push_back
#define N 1000000
using namespace std;
typedef long long ll;
ll n, m, i, j, a, b, t, ans, prim[N], k;
ifstream fin("pinex.in");
ofstream fout("pinex.out");
char ciur[1000100];
void faciur()
{
	ciur[0]=ciur[1]=1;
	for(ll i=2;i*i<=N;++i)
		if(ciur[i]==0)
		for(ll j=2;j*i<=N;++j)
			ciur[i*j]=1;
	for(ll i=1;i<=N;++i)
		if(!ciur[i])
			prim[++k]=i;
}
int main()
{
	fin>>t;
	faciur();
	while(t)
	{
		--t;
		fin>>a>>b;
		ll d=2;
		ans=0;
		vector<ll> dvz, nr;
		for(i=1;prim[i]*prim[i]<=b&&i<=k;++i)
		{
			if(b%prim[i]==0)
				dvz.pb(prim[i]);
			while(b%prim[i]==0)
				b/=prim[i];
		}
		if(b>1)
			dvz.pb(b);
		for(auto i:dvz)
			nr.pb(a/i);
		//for(i=0;i<nr.size();++i)
		//	fout<<dvz[i]<<' '<<nr[i]<<'\n';
		for(i=1;i<(1<<dvz.size());++i)
		{
			ll ci=i, d=__builtin_popcount(i), aux=1;
			if(d%2)
				d=+1;
			else d=-1;
			int p=0;
			while(ci)
			{
				if(ci%2)
					aux*=dvz[p];
				++p;
				ci/=2;
			}
			ans+=d*a/aux;
		}
		fout<<a-ans<<'\n';
	}
}