#include <algorithm>
using namespace std;

#define ll long long
#define MAX 1000005
#define DIM 78505
#define LIM 35

int prim[DIM];
ll fact[DIM];
bool v[MAX];
int t,m;
ll a,b;

void ciur ()
{
	int i,j;
	
	for (i=2; i<MAX; ++i)
		if (!v[i])
		{
			prim[++m]=i;
			for (j=2*i; j<MAX; j+=i)
				v[j]=1;
		}
}

ll solve ()
{
	ll d,nrt,prod;
	int nr,i,j,ok;
	
	for (nr=0, i=1; prim[i]*prim[i]<=b && i<=m; ++i)
		if (b%prim[i]==0)
			for (fact[++nr]=prim[i]; b%prim[i]==0; b/=prim[i]);
	if (b>1)
			fact[++nr]=b;
	nrt=a;
	for (i=1; i<(1<<nr); ++i)
	{
		for (ok=j=0, prod=1; j<nr; ++j)
			if (i&(1<<j))
			{
				prod*=fact[j+1];
				ok=(ok+1)%2;
			}
		if (ok)
			nrt-=a/prod;
		else
			nrt+=a/prod;
	}
	return nrt;
}

int main ()
{
	freopen ("pinex.in","r",stdin);
	freopen ("pinex.out","w",stdout);
	ll i;
	
	ciur ();
	scanf ("%d",&t);
	for (i=1; i<=t; ++i)
	{
		scanf ("%lld%lld",&a,&b);
		printf ("%lld\n",solve ());
	}
	
	return 0;
}