#include <iostream>
#include <cstdio>
#include <vector>
#include <cmath>
using namespace std;

vector<int> gen_primes(int n)
{
	vector<bool> sieve(n+1, true);
	vector<int> primes;
	for (int p = 2; p <= n; p++) {
		if (!(sieve[p])) {
			continue;
		}
		primes.push_back(p);
		for (int i = 2*p; i <= n; i += p) {
			sieve[i] = false;
		}
	}
	return primes;
}

vector<long long> factorize(long long n, const vector<int> & primes)
{
	vector<long long> prime_factors;
	int sqrtn = sqrt(n);
	for (auto p: primes) {
		if (p > sqrtn) {
			break;
		}
		if (n % p != 0) {
			continue;
		}
		prime_factors.push_back(p);
		do {
			n /= p;
		} while (n % p == 0);
		sqrtn = sqrt(n);
	}
	if (n != 1) {
		prime_factors.push_back(n);
	}
	return prime_factors;
}

int main()
{
	ios::sync_with_stdio(false);
	freopen("pinex.in", "r", stdin);
	freopen("pinex.out", "w", stdout);
	vector<int> primes = gen_primes(1e6);
	int ntest;
	cin >> ntest;
	for (int test = 0; test < ntest; test++) {
		long long m, n;
		cin >> m >> n;
		vector<long long> prime_factors = factorize(n, primes);
		vector<long long> nmul(1<<prime_factors.size());
		nmul[0] = m;
		long long ans = m;
		for (int i = 1; i < nmul.size(); i++) {
			int lsb = i & -i;
			nmul[i] = nmul[i^lsb]/prime_factors[__builtin_ctz(lsb)];
			if (__builtin_parity(i)) {
				ans -= nmul[i];
			}
			else {
				ans += nmul[i];
			}
		}
		printf("%lld\n", ans);
	}
	return 0;
}