#include <stdio.h>

#define ll long long

ll M, A, B;

inline ll cmmdc(ll a, ll b) {
	ll r;
	while (a % b != 0) {
    	r = a % b;
		a = b;
		b = r;
	}

	return b;
}

int main() {

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

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

		ll sol = 0;
		for (ll j = 1; j <= A; j++)
			if (cmmdc(j, B) == 1) sol++;
		printf("%lld\n", sol);
	}

	return 0;
}