#include <cstdio>
#include <cstdlib>
#include <cassert>
#include <vector>
#include <cstring>
#include <cctype>
#include <algorithm>
using namespace std;
typedef long long LL;

#ifdef INFOARENA
#define ProblemName "pinex"
#endif

#define MCONCAT(A, B) A B
#ifdef ProblemName
#define InFile MCONCAT(ProblemName, ".in")
#define OuFile MCONCAT(ProblemName, ".out")
#else
#define InFile "fis.in"
#define OuFile "fis.out"
#endif

#define MAXN 1000010
int primes[MAXN / 2], pnr;

/*
int physical[(MAXN >> 6) + 1];

inline int getp(int n) {
	return physical[n >> 6] & (1 << ((n >> 1) & 31));
}

inline void setp(int n) {
	physical[n >> 6] |= (1 << ((n >> 1) & 31));
}

void ciur() {
	pnr = 0;
	memset(physical, 0, sizeof(physical));
	primes[pnr++] = 2;
	int SQLIM = (int)sqrt(MAXN) + 1;
	for (int d = 3; d < SQLIM; d += 2) {
		if (getp(d)) continue;
		primes[pnr++] = d;
		for (int i = d * d, k = d * 2; i < MAXN; i += k)
			setp(i);
	}
	for (int d = SQLIM; d < MAXN; ++d)
	if (!getp(d))
		primes[pnr++] = d;
}*/

int marked[MAXN / 2 / 8 + 1];

void ciur() {
	int n = MAXN;
	int i, j;
	primes[0] = 2;
	pnr = 1;
	for (i = 1; ((i * i) << 1) + (i << 1) <= n; i += 1) {
		if ((marked[i >> 3] & (1 << (i & 7))) == 0) {
			for (j = ((i * i) << 1) + (i << 1); (j << 1) + 1 <= n; j += (i << 1) + 1) {
				marked[j >> 3] |= (1 << (j & 7));
			}
		}
	}
	for (i = 1; 2 * i + 1 <= n; ++i)
	if ((marked[i >> 3] & (1 << (i & 7))) == 0)
		primes[pnr++] = i * 2 + 1;
}

#define MAXDIVS 100
LL divs[MAXDIVS], dnr;

LL solve(LL A, LL B) {
	dnr = 0;
	for (int i = 0; i < pnr; ++i) {
		int p = primes[i];
		if (1LL * p * p > B) break;
		if (B % p == 0)
			divs[dnr++] = p;
		while (B % p == 0)
			B /= p;
	}
	if (B > 1)
		divs[dnr++] = B;
	LL ans = 0;
	int lim = 1 << dnr;
	for (int mask = 1; mask < lim; ++mask) {
		int cnt = 0;
		LL prod = 1;
		for (int i = 0; i < dnr; ++i)
		if (mask & (1 << i)) {
			++cnt;
			prod *= divs[i];
		}
		if (cnt & 1)
			ans += A / prod;
		else ans -= A / prod;
	}
	return ans;
}

int main() {
	assert(freopen(InFile, "r", stdin));
	assert(freopen(OuFile, "w", stdout));
	ciur();
	int M;
	scanf("%d", &M);
	while (M--) {
		LL A, B;
		scanf("%lld%lld", &A, &B);
		printf("%lld\n", A - solve(A, B));
	}
	return 0;
}