#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, d=2; d*d<=b; ++d)
		if (b%d==0)
			for (fact[++nr]=d; b%d==0; b/=d);
	if (b>1)
			fact[++nr]=b;
	nrt=0;
	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);
	int i;
	
	ciur ();
	scanf ("%d",&t);
	for (i=1; i<=t; ++i)
	{
		scanf ("%lld%lld",&a,&b);
		printf ("%lld\n",a-solve ());
	}
	
	return 0;
}