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

#define ll long long 

ll M, A, B, fact[30];

void solve() {
	ll t = 0, d = 2;
	while (B > 1) {
    	if (B % d == 0) {
			fact[++t] = d;
        	while (B % d == 0)
			B /= d;
		}

		if (d > sqrt(B) && B > 1) {
        	fact[++t] = B;
			B = 1;
		}

		if (d == 2) d++;
		else d += 2;
	}

	ll sol = A;
	for (int i = 1; i < (1 << t); i++) {
		ll nr = 0, prod = 1;
		for (int j = 0; j < t; j++)
			if ((1 << j) & i) {
				prod = 1LL * prod * fact[j + 1];
				nr++;
			}

		if (nr % 2) nr = -1;
		else nr = 1;

		sol = sol + 1LL * nr * A / prod;
	}

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

int main() {

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

	scanf("%lld", &M);
	for (int i = 1; i <= M; i++) {
    	scanf("%lld %lld", &A, &B);
		solve();
	}

	return 0;
}