#include <cstdio>
#include <cmath>

using namespace std;

const int MAXP=1000005;
bool ciur[MAXP];
int primes[100000];

void sieve(void)
{
	int lim=(int)sqrt(1.0 * MAXP);
	for(int i=4;i<=MAXP;i+=2)
		ciur[i]=true;
	for(int i=3;i<=lim;i+=2)
		if(!ciur[i])
			for(int j=i*i;j<=MAXP;j+=2*i)
				ciur[j]=true;
	int k=0;
	for(int i=2;i<=MAXP;i++)
		if(!ciur[i])
			primes[k++]=i;
}

int nrprimes;
long long fact[20];

void prime_fact(long long n)
{
	int i=0;
	int lim=(int)sqrt(1.0 * n);
	nrprimes=0;
	while(n>1 && primes[i]<=lim)
	{
		bool ok=false;
		while(n%primes[i]==0)
		{
			n/=primes[i];
			ok=true;
		}
		if(ok)
		{
			fact[nrprimes++]=primes[i];
			lim=(int)sqrt(1.0 * n);
		}
		i++;
	}
	if(n>1)fact[nrprimes++]=n;
}

long long PINEX(long long x)
{
	long long ans=0;
	int ns=1<<nrprimes;
	for(int i=1;i<ns;i++)
	{
		int c=i;
		long long p=1;
		int nr=0, cardinal=0;
		while(c)
		{
			if(c&1)
			{
				p*=fact[nr];
				cardinal++;
			}
			nr++;
			c>>=1;
		}
		if(cardinal%2==0)ans-=x/p;
		else ans+=x/p;
	}
	ans=x-ans;
	return ans;
}

int main()
{
    freopen("pinex.in", "r", stdin);
    freopen("pinex.out", "w", stdout);

    sieve();

    int nr_test;
    scanf("%d", &nr_test);

    for(int k=0;k<nr_test;k++)
	{
		long long x, y;
		scanf("%lld%lld", &x, &y);
		prime_fact(y);
		printf("%lld\n", PINEX(x));
	}
    return 0;
}