#include <cstdio>

#define FIN "pinex.in"
#define FOUT "pinex.out"

#define MAXP 500
#define MAXN 1000001

int M, B, P;
long long A, R;
int V[MAXP], Div[MAXP];
char D[MAXN];

void calc()
{
	int i, j;
	
	for (i = 4; i < MAXN; i += 2)
		D[i] = 1;
	for (i = 3; i * i < MAXN; i += 2)
		if (!D[i])
			for (j = i * i; j < MAXN; j += i)
				D[j] = 1;
	
	V[1] = 2; P = 1;
	for (i = 3; i < MAXN; i += 2)
		if (!D[i])
			V[++ P] = i;
}

void back(int Pr, int L, int X)
{
	int i;

	if (L % 2)
		R += A / Pr;
	else if (L)
		R -= A / Pr;
	
	if (L == Div[0])
		return;	
	for (i = X + 1; i <= Div[0]; ++ i)
		if (Pr % Div[i])
			back(Pr * Div[i], L + 1, i);
}

int main()
{
	int i, j;
	
	freopen(FIN, "r", stdin);
	freopen(FOUT, "w", stdout);
	
	scanf("%d", &M);
	calc();	
	
	for (i = 1; i <= M; ++ i)
	{
		scanf("%lld %d", &A, &B);
		
		for (j = 1, Div[0] = 0; B > 1; ++ j)
			if (B % V[j] == 0)
			{
				Div[++ Div[0]] = V[j];
				
				while (B % V[j] == 0)
					B /= V[j];
			}
		
		R = 0; back(1, 0, 0);
		printf("%lld\n", A - R);
	}
}