#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 cit ()
{
	scanf ("%lld", &A);
	scanf ("%lld", &B);
	sqb = sqrt (B);
}

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 div ()
{
	int i, d;
	D[0] = 0;
	for (i = 1; i <= ciur[0] && ciur[i] <= sqb; 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 cmb (int k)
{
	if (k - 1 == K)
	{
		if (K & 1)
			R += A / P;
		else
			R -= A / P;
		return;
	}
	
	for (int i = X[k-1]+1; i <= D[0]; i++)
	{
		X[k] = i;
		P *= D[i];
		cmb (k + 1);
		P /= D[i];
	}	
}

void pie ()
{
	for (K = P = 1, R = 0; K <= D[0]; K++)
	{
		cmb (1);		
	}
	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;
}