#include <bits/stdc++.h>

using namespace std;

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

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

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

	for(int64_t div = 2; div * div <= b; div++) {
		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
	int64_t 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);
	}

	cout << a - sum << '\n';

	return;
}

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