#include <bits/stdc++.h>

using namespace std;
#define int long long int
#define N 1000006

int t, ciur[N], a, b;

vector<int> prime;

void eratostene() {
	ciur[0] = ciur[1] = 1;
	for (int i = 2; i * i < N; i++)
		if (!ciur[i])
			for (int j = 2; j * i < N; j++)
				ciur[i * j] = 1;
	for (int i = 2; i < N; i++)
		if (!ciur[i])
			prime.emplace_back(i);
}

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

	cin.tie(0)->sync_with_stdio(false);

	eratostene();
	cin >> t;
	while (t--) {
		cin >> a >> b;
		vector <int> factori;
		int d = prime[0], l = 0;
		while (b > 1 && d * d <= b) {
			if (b % d == 0) {
				factori.emplace_back(d);
				while (b % d == 0) {
					b /= d;
				}
			}
			d = prime[++l];
		}
		if (b > 1)
			factori.emplace_back(b);
		int nr_div = factori.size();
		int pinex = 0;
		int giani = 1;
		for (int mask = 1; mask < (1 << nr_div); mask++) {
			int biti = __builtin_popcountll(mask);
			giani = 1;
			for (int p = 0; p < nr_div; p++) {
				if (mask & (1 << p)) {
					giani *= factori[p];
				}
			}
			int multipli = a / giani;
			if (biti % 2)
				pinex += multipli;
			else
				pinex -= multipli;
		}
		cout << a - pinex << '\n';
	}

    return 0;
}