#include <stdio.h>
#define NMAX 10000

long long fact[NMAX + 1];
long long A, B, M, nr;

void div()
{
	int i;
	nr = 0;
	for (i = 2; i <= B; ++i) {
		if (B % i == 0) {
			fact[++nr] = i;
			while (B % i == 0)
				B /= i;
		}
	}
}

void solve()
{
	int i, j;
	div();
	long long sol = A;
	for (i = 1; i < (1 << nr); ++i) {
		long long prod = 1;
		int sign = 0;
		for (j = 0; j < nr; ++j)
			if ((1 << j) & i) {
				prod = 1LL * prod * fact[j + 1];
				++sign;
			}

		if (sign % 2)
			sign = -1;
		else sign = 1;
		sol = sol + 1LL * sign * (A / prod);
	}

	printf("%lld\n", sol);
}

int main()
{
	freopen("pinex.in", "r", stdin);
	freopen("pinex.out", "w", stdout);

	scanf("%lld", &M);
	for ( ; M; --M) {
		scanf("%lld %lld", &A, &B);
		solve();
	}
	return 0;
}