#include <cstdio>

const long long MAX = 1000000;

int m, d, P[MAX];
long long a, b, k, DIV[30];

void precalc (), divizori (), pinex ();

int main () {
	
	freopen ("pinex.in", "r", stdin);
	freopen ("pinex.out", "w", stdout);
	
	precalc ();
	
	scanf ("%d", &m);
	
	while (m--) {
		scanf ("%lld %lld", &a, &b);
		
		divizori ();
		
		pinex ();
	}
}

void precalc () {
	
	int i, j;
	
	for (i = 2; i < MAX; i++)
		if (!P[i]) {
			P[++k] = i;
			for (j = 2 * i; j < MAX; j += i)
				P[j] = 1;
		}
}

void divizori () {
	
	long long i, x = b;
	
	for (i = 1, d = 0; i <= k && i * i <= b; i++) {
		if (x % P[i] == 0) {
			DIV[++d] = P[i];
			while (x % P[i] == 0)
				x /= P[i];
		}
	}
	if (x != 1)
		DIV[++d] = x;
}

void pinex () {
	
	long long i, j, prod, nr, sol = 0;
	
	for (i = 1; i < (1LL << d); i++) {
		nr = 0, prod = 1;
		for (j = 0; j < d; j++)
			if (i & (1 << j)) {
				prod = 1LL * prod * DIV[j+1];
				nr++;
			}
		
		if (nr % 2) nr = 1;
		else nr = -1;
		
		sol += nr * a / prod;
	}

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