#include <bits/stdc++.h>
#define pb push_back
using namespace std;
typedef long long ll;
ll n, m, i, j, a, b, t, ans;
ifstream fin("pinex.in");
ofstream fout("pinex.out");
int main()
{
	fin>>t;
	while(t)
	{
		--t;
		fin>>a>>b;
		ll d=2;
		ans=0;
		vector<ll> dvz, nr;
		while(d*d<=b)
		{
			int p=0;
			while(b%d==0)
			{
				++p;
				b/=d;
			}
			if(p)
				dvz.pb(d);
			++d;
		}
		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';
	}
}