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

void solve() {
	int64_t a, 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

	int64_t ans = 0;
	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 << a - ans << '\n';
}

int main() {
	init_primes();

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