#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;
}

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("%I64d%I64d", &x, &y);
		prime_fact(y);

		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;
		printf("%I64d\n", ans);
	}
    return 0;
}