#include <stdio.h>

#define P_MAX 1000000
#define NP_MAX 100000

char ciur[P_MAX + 1];
int compact[NP_MAX];
int sp;

void Erathostenes()
{
	for (int i = 2; i <= P_MAX; ++i) {
		if (!ciur[i]) {
			for (int j = 2 * i; j <= P_MAX; j += i) {
				ciur[j] = 1;
			}
		}
	}
}

void MakeCompact()
{
	for (int i = 2; i <= P_MAX; ++i) {
		if (!ciur[i]) {
			compact[++sp] = i;
		}
	}
}

int dp[25];

int main()
{
	FILE *fin, *fout;
	fin = fopen("pinex.in", "r");
	fout = fopen("pinex.out", "w");

	Erathostenes();
	MakeCompact();

	int M;
	fscanf(fin, "%d", &M);

	int t;
	for (t = 0; t < M; ++t) {
		long long A, B;
		fscanf(fin, "%lld%lld",  &A, &B);
		int np = 0, reach = 1;
		while (reach <= sp && compact[reach] * compact[reach] <= B) {
			if (B % compact[reach] == 0) {
				dp[++np] = compact[reach];
				while (B % compact[reach] == 0) {
					B /= compact[reach];
				}
			}
			++reach;
		}
		if (B > 1) {
			dp[++np] = B;
		}
		long long mm = (1 << np);
		long long sum = 0;
		for (long long i = 0; i < mm; ++i) {
			long long sgn = -1, thing = 1;
			for (int j = 0; j < np; ++j) {
				sgn *= ((i >> j) & 1) ? -1 : 1;
				thing *= ((i >> j) & 1) ? dp[j + 1] : 1;
			}
			sum += sgn * (A / thing);
		}
		fprintf(fout, "%lld\n", -sum);
	}

	fclose(fin);
	fclose(fout);
	return 0;
}