#include <bits/stdc++.h>

using namespace std;

typedef long long int lli;

const int MAXM = 5e2;
const lli MAXA = 1e18;
const lli MAXB = 1e12;

vector<lli> primes;


vector<lli> calcCiur(lli n) {
	vector<lli> primes;
	bool ciur[n + 2];
	memset(ciur, 0, sizeof(ciur));

	ciur[0] = ciur[1] = true;

	primes.push_back(2);
	for (lli i = 4; i <= n; i += 2) {
		ciur[i] = true;
	}

	for (lli i = 3; i <= n; i += 2) {
		if (!ciur[i]) {
			primes.push_back(i);
			for (int j = i + i; j <= n; j += i) {
				ciur[j] = true;
			}
		}
	}

	return primes;
}

vector<lli> primeFactors(lli b) {
	vector<lli> factors;

	for (auto x : primes) {
		if (x * x > b)
			break;
		
		if (b % x == 0)
			factors.push_back(x);

		while (b % x == 0)
			b /= x;
	}

	if (b > 1)
		factors.push_back(b);

	return factors;
}

lli pinex(lli a, lli b) {
	lli ans = 0;
	vector<lli> factors = primeFactors(b);

	int n = factors.size();

	lli prod = 1;
	int cnt = 0;

	for (lli mask = 1; mask < (1 << n); ++ mask) {
		cnt = 0;
		prod = 1;
		for (lli i = 0; i < n; ++ i) {
			if ((1 << i) & mask) {
				prod *= factors[i];
				++ cnt;
			}
		}

		if (cnt % 2) ans += a / prod;
		else ans -= a / prod;
	}

	ans = a - ans;

	return ans;
}

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

	primes = calcCiur(1e6);

	int m;
	lli a, b;

	cin >> m;

	while (m --) {
		cin >> a >> b;
		cout << pinex(a, b) << '\n';
	}


	return 0;
}