#include <bits/stdc++.h>
#define ll long long 
#pragma GCC optimize("03")

using namespace std;

ifstream in("pinex.in");
ofstream out("pinex.out");

int t, vf;
ll a, b, st[20];
bitset <1000100> viz;
vector <ll> primes;

void prec() {
	for (int i = 2; i <= 1000000; i++)
		if (!viz[i]) {
			primes.push_back(i);
			for (int j = i + i; j <= 1000000; j += i)
				viz[j] = 1;
		}
}

void solve(ll a, ll b) {
	ll ans = 0;
	vf = 0;
	for (auto i : primes) {
		if (i * i > b)
			continue;
		if (b % i)
			continue;
		while (b % i == 0) 
			b /= i;
		st[vf++] = i;
	}
	if (b > 1)
		st[vf++] = b;
	for (int mask = 1; mask < (1 << vf); mask++) {
		ll val = 1;
		int cnt = 0;
		for (int bit = 0; bit < vf; bit++)
			if (mask & (1 << bit)) {
				cnt++;
				val *= st[bit];
			}
		if (cnt & 1)
			ans += a / val;
		else ans -= a / val;
	}
	out << a - ans << '\n';
}

int main() {
	prec();
	in >> t;
	while (t--) {
		in >> a >> b;
		solve(a, b);
	}
	return 0;
}