#include <bits/stdc++.h>

using namespace std;

#ifndef LOCAL
ifstream in("pinex.in");
ofstream out("pinex.out");
#define cin in
#define cout out
#endif

vector<int> primes;
void init_primes() { // Ciurul lui eratostene clasic
	const int nmax = 1e6 + 7;
	vector<bool> is_prime(nmax, true);

	is_prime[0] = false; is_prime[1] = false;
	for(int p = 2; p < nmax; p++) {
		if(is_prime[p]) {
			primes.push_back(p);
			for(int64_t i = 1LL * p * p; i < nmax; i += p) {
				is_prime[i] = false;
			}
		}
	}
}

int64_t ans = 0, a;
void backtrack(vector<int64_t>& b_factors, int poz, int sign, int64_t prod) {
	if(poz == b_factors.size()) {
		// am ajuns la final
		ans += sign * (a / prod);
		return;
	}

	backtrack(b_factors, poz + 1, sign, prod); // cazul in care nu luam b_factors[poz]
	backtrack(b_factors, poz + 1, -sign, prod * b_factors[poz]); // cazul in care luam b_factors[poz]
}

void solve() {
	int64_t b; cin >> a >> b;

	// Trebuie sa gasim factorii primi ai lui b

	vector<int64_t> b_factors;
	for(int p : primes) {
		if(1LL * p * p > b) { // daca p devine mai mare decat sqrt(b) putem da break devreme
			break;
		}

		if(b % p == 0) {
			b_factors.push_back(p);
			while(b % p == 0) {
				b /= p;
			}
		}
	}

	if(b > 1) {
		// mai avem si un numar prim > 1e6
		b_factors.push_back(b);
		b = 1;
	}

	// Varianta 1 -> masti pe biti

	int n = b_factors.size(); // numarul de divizori primi

	ans = 0;
	backtrack(b_factors, 0, 1, 1); // O(2 ^ n)

	// Are complexitate O(2 ^ n * n)
	/* for(int mask = 1; mask < (1 << n); mask++) {
		int sign = -1;
		int64_t prod = 1;

		for(int i = 0; i < n; i++) {
			int ales = (mask >> i) & 1; // alegem sau nu factorul prim i

			if(ales) {
				sign *= -1;
				prod *= b_factors[i];
			}
		}

		ans += sign * (a / prod);
	} */

	cout << ans << '\n';
}

int main() {
	init_primes();

	int m; cin >> m;
	for(int test = 0; test < m; test++) {
		solve();
	}
}