#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>

using namespace std;

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

const int PMAX = 1e6 + 7;
vector<int64_t> small_primes;
void init_small_primes() {
	bitset<PMAX> is_prime;
	// is_prime[p] == 0 inseamna ca p e prim

	is_prime[0] = is_prime[1] = 1;
	for(int p = 2; p < PMAX; p++) {
		if(is_prime[p] == 0) {
			// am gasit un numar prim nou, vom itera prin multiplii lui
			small_primes.push_back(p);

			for(int64_t d = 1LL * p * p; d < PMAX; d += p) {
				is_prime[d] = 1; // multiplul clar _NU_ este prim
			}		
		}
	}
}

int64_t sum = 0, a;
void bkt(vector<int64_t>& factori_primi, int poz, int64_t sign, int64_t prod) {
	if(poz == factori_primi.size()) {
		sum += sign * (a / prod);
		return;
	}

	bkt(factori_primi, poz + 1, sign, prod); // nu am ales sa il includ pe factori_primi[poz]
	bkt(factori_primi, poz + 1, -1 * sign, prod * factori_primi[poz]); // am ales sa il includ pe factori_primi[poz]
}

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

	// trebuie sa il factorizam pe b
	vector<int64_t> factori_primi;

	for(auto div : small_primes) { // inainte era O(sqrt(B)) acum este O(numere prime pana la sqrt(B)) = O(sqrt(B) / log(B))
		if(div * div > b) break;

		if(b % div == 0) {
			// div divide b -> div este un alt factor prim
			factori_primi.push_back(div);
		}

		// il reducem pe div din b
		while(b % div == 0) {
			b /= div;
		}
	}

	// ne mai ramane cazul cand b > 1, deci si el acum este un propriu factor prim
	if(b > 1) {
		factori_primi.push_back(b);
		b = 1;
	}

	assert(factori_primi.size() <= 12); // stim asta din constructia 2 * 3 * 5 * .... * 31

	// acum trebuie pentru fiecare subset al vectorului factori_primi sa vedem
	// 1. cate elemente are -> coeficientul de +-1
	// 2. produsul elementelor -> A / (d1 * d2 * ... * dk)

	// Varianta 1 -> O(2^N * N)
	sum = 0;
	
	/* for(int mask = 1; mask < (1 << factori_primi.size()); mask++) {
		int64_t sign = -1, prod = 1;
	
		for(int i = 0; i < factori_primi.size(); i++) {
			int ales = (mask >> i) & 1; // am ales sau nu factorul prim d[i] in subsetul nostru curent?

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

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

	// Varianta 2 -> Backtracking
	bkt(factori_primi, 0, 1, 1);

	cout << sum << '\n';

	return;
}

int main() {
	init_small_primes();

	ios_base::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);

	int t; cin >> t;
	for(int test = 1; test <= t; test++) {
		solve();
	}
}