#include<cstdio>
#include<bitset>
#include<vector>
using namespace std;
#define NP 1000000
#define pb push_back
#define LL long long
#define sh short int
bitset<NP>viz;
vector<int>prim;
int g;
LL B,A;
void ciur()
{
	int d=2;
	while (d*d<NP)
	{
		if (viz[d])
		{
			++d;
			continue;
		}
		for (int i=d*d; i<NP; i+=d)
			viz[i]=1;
		prim.pb(d);
		++d;
	}
	for (int i=d; i<NP; ++i)
		if (!viz[i])
			prim.pb(i);
	g=prim.size();
}
void divizori(LL x)
{
	int i;
	vector<LL>diviz(0);
	diviz.clear();
	for (i=0; i<g && x!=1 && prim[i]*prim[i]<=x; ++i)
	{
		if (x%prim[i])
			continue;
		while (x%prim[i]==0)
			x/=prim[i];
		diviz.pb(prim[i]);
	}
	if (x!=1)
		diviz.pb(x);
	x=diviz.size();
	LL N=1<<x,rez=A;
	for (i=1; i<N; ++i)
	{
		LL prod=1;
		LL nrd=0;
		for (int j=0; j<x; ++j)
			if ((1<<j)&i)
			{
				prod*=diviz[j];
				++nrd;
			}
		if (nrd&1)
			nrd=-1;
		else
			nrd=1;
		rez+=nrd*A/prod;
	}
	printf("%lld\n",rez);
}
int main()
{
	freopen("pinex.in","r",stdin);
	freopen("pinex.out","w",stdout);
	sh t;
	scanf("%hd",&t);
	ciur();
	while (t--)
	{
		scanf("%lld%lld",&A,&B);
		divizori(B);
	}
	return 0;
}