// sursa asa la sto sa vad cat ia mobius
#include <bits/stdc++.h>

using namespace std;

ifstream fin("pinex.in");
ofstream fout("pinex.out");

const long long BMAX = 1e12;
const int SQRTBMAX = 1e6;

int T;
char prime[SQRTBMAX + 1];
vector<int> primes;

void seive(int n = SQRTBMAX) {
	prime[0] = prime[1] = 1;

	primes.push_back(2);
	for(int i = 4; i <= n; i += 2) {
		prime[i] = 1;
	}

	for(int i = 3; i <= n; i += 2) {
		if(prime[i] == 0) {
			primes.push_back(i);

			if((long long) i * i <= n) {
				for(int j = i * i; j <= n; j += 2 * i) {
					prime[i] = 1;
				}
			}
		}
	}
}

void solve() {
	long long A, B;
	fin >> A >> B;

	vector<int> p;

	for(int i = 0; i < (int) primes.size() && (long long) primes[i] * primes[i] <= B; i++) {
		if(B % primes[i] == 0) {
			p.push_back(primes[i]);

			while(B % primes[i] == 0) {
				B /= primes[i];
			}
		}
	}

	if(B > 1) {
		p.push_back(B);
	}

	int ans = A;

	for(int i = 1; i < (1 << p.size()); i++) {
		long long d = 1;
		int mob = 1;

		for(int j = 0; j < (int) p.size(); j++) {
			if(i & (1 << j)) {
				d *= p[j];
				mob = -mob;
			}
		}

		ans += A / d * mob;
	}

	fout << ans << '\n';
}

int main() {
	fin >> T;

	seive();

	for(int tc = 1; tc <= T; tc++) {
		solve();
	}
	return 0;
}