#include <bits/stdc++.h>
using namespace std;
 
ifstream fin("pinex.in");
ofstream fout("pinex.out");

using ll = long long;
const int MAX = 1e6;
 
bool sieve[MAX + 5];
vector<ll> prime, fact;

ll calc(ll A, ll B) {
	fact.clear();
	int i = 0;
	while(prime[i] * prime[i] <= B) {
		if(B % prime[i] == 0) {
			fact.push_back(prime[i]);
			while (B % prime[i] == 0)
				B /= prime[i];
		}
		i++;
	}
	if (B > 1) 
		fact.push_back(B);

	int N = fact.size();
	ll ans = 0;
	for(int mask = 0; mask < (1 << N); ++mask) {
		ll P = 1;
		int cnt = 0;
		for(i = 0; i < N; ++i)
			if(mask & (1 << i)) {
				cnt++; 
				P *= fact[i];
			}
		if(cnt % 2) 
			ans += A / P;
		else if(cnt > 0) 
			ans -= A / P;
	}

	return A - ans;
}

int main() {
	for(int i = 2; i <= MAX; ++i)
		if(!sieve[i]) {
			prime.push_back(1ll * i);
			for(int j = i; j <= MAX; j += i)
				 sieve[j] = 1;
		}

	int Q;
	fin >> Q;
	while (Q--) {
		ll x, y;
		fin >> x >> y;
		fout << calc(x, y) << '\n';
	}
 
	return 0;
}