#include <cstdio>
#include <cstring>

#define MAXPRIME 1000000
#define PRIME_SIZE 80000

long long primes[PRIME_SIZE];
int pcnt;

void precompute_primes(int n)
{
	pcnt = 0;
	int *val = new int[n/32+1];
	memset(val,0,sizeof(int)*(n/32+1));
	pcnt=0;
	primes[pcnt++] = 2;
	bool stop = false;

	for (int i=3;i*i<=n;i+=2)
		if (!((val[i/32]>>(i%32))&1))
		{
			primes[pcnt++] = i;
			if (i*i > n) stop = true;
			if (stop) continue;

			for (int j=i*i;j<=n;j+=i<<1)
				val[j/32] |= 1<<(j%32);
		}

	delete val;
}

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

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

	precompute_primes(MAXPRIME);

	for(;m;m--)
	{
		long long a,b;
		scanf ("%lld%lld",&a,&b);
		long long bdivs[32];
		int kd = 0;

		for (int i=0;i<pcnt && (long long)primes[i]*primes[i] <= b;i++)
		{
			if (b%primes[i] == 0) bdivs[kd++] = primes[i];
			while (b%primes[i] == 0) b/=primes[i];
		}

		if (b > 1) bdivs[kd++] = b;

		long long rez = 0;

		for (int i=1;i<(1<<kd);i++)
		{
			long long prod = 1;
			long long t = i,cnt = 0, bits = 0;
			for (;t;t>>=1,cnt++) 
				if (t&1)
					prod*=bdivs[cnt], bits++;

			if (bits&1) rez += a/prod;
			else rez -= a/prod;
		}
		printf ("%lld\n",a-rez);
	}
	return 0;
}