#include <cstdio>
#include <cmath>
#include <cstring>
#include <ctime>

#define MAXPRIME 1000000
#define PRIME_SIZE 80000

int 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<=n;i+=2)
		if (!((val[i/32]>>(i%32))&1))
		{
			primes[pcnt++] = i;
			if (stop) continue;
			if (i*i > n) stop = true;			

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

	delete val;
}

int main()
{
	//clock_t t0 = clock();
	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;
		int t = (int)sqrt((double)b);

		for (int i=0;i<pcnt && primes[i]<= t && b > 1;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;
		//printf ("%d\n",kd);
		for (int i=1;i<(1<<kd);i++)
		{
			long long prod = 1;
			long long cnt = 0, bits = 0;
			for (int j=0;j<kd;j++)
				if (i&(1>>j))
					prod*=bdivs[j], bits++;

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

	//clock_t t1 = clock();
	//printf ("%lf\n",(double)(t1-t0)/CLOCKS_PER_SEC);
	return 0;
}