#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
#define SQLIM 1010
int primes[MAXN / 2], pnr;

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

#define getp(n) (physical[n >> 6] & (1 << ((n >> 1) & 31)))
#define setp(n) (physical[n >> 6] |= (1 << ((n >> 1) & 31)))

void ciur() {
	pnr = 0;
	//memset(physical, 0, sizeof(physical));
	primes[pnr++] = 2;
	register int i, d, k;
	for (d = 3; d < SQLIM; d += 2) {
		if (getp(d)) continue;
		primes[pnr++] = d;
		for (i = d * d, k = d * 2; i < MAXN; i += k)
			setp(i);
	}
	for (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;
}*/

unsigned int prime[MAXN / 64];
#define gP(n) (prime[n>>6]&(1<<((n>>1)&31)))
#define rP(n) (prime[n>>6]&=~(1<<((n>>1)&31)))
void ciur()
{
	memset(prime, -1, sizeof(prime));
	pnr = 0;
	primes[pnr++] = 2;

	unsigned int i;
	unsigned int sqrtN = (unsigned int)sqrt((double)MAXN) + 1;
	for (i = 3; i < sqrtN; i += 2) if (gP(i))
	{
		primes[pnr++] = i;
		unsigned int i2 = i + i;
		for (unsigned int j = i * i; j < MAXN; j += i2) rP(j);
	}
	for (int i = sqrtN; i < MAXN; ++i) if (gP(i))
		primes[pnr++] = i;
}

#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;
}