#include <stdio.h>
#include <math.h>

const int DIM = 1000000;
int ciur[DIM], D[10], X[10], sqb, K, M;
long long A, B, R, P;

void era ()
{
	int i, j;
	for (i = 2; i <= DIM; i++)
		if (!ciur[i])
		{
			ciur[++ciur[0]] = i;
			for (j = i+i; j <= sqb; j += i)
				ciur[j] = 1;
		}	
}

void cit ()
{
	scanf ("%lld", &A);
	scanf ("%lld", &B);
	sqb = sqrt (B);
	R = D[0] = 0;
}

void div ()
{
	int i, d;
	for (i = 1; i <= ciur[0] && ciur[i] <= sqb && B != 1; i++)
	{
		d = ciur[i];
		if (B % d == 0)
			D[++D[0]] = d;
		while (B % d == 0)
			B /= d;
	}
	if (B != 1)
		D[++D[0]] = B;
}

void pie ()
{
	int x, d, j, nr;
	for (x = 1; x < 1<<D[0]; x++)
	{
		d = 1, nr = 0;
		for (j = 0; j < D[0]; j++)
			if ((1 << j) & x)
			{
				nr++;
				d *= D[j+1];
			}
		if (nr & 1)
			R += A / d;
		else
			R -= A / d;
	}
	printf ("%lld\n", A - R);
}

int main ()
{
	freopen ("pinex.in", "r", stdin);
	freopen ("pinex.out", "w", stdout);
	
	era ();
	scanf ("%d", &M);
	while (M--)
	{
		cit ();
		div ();
		pie ();
	}
	
	return 0;
}