#include <bits/stdc++.h>

template <std::size_t N, class Arr> struct eratostene {
	std::vector<int> primes;
	
	eratostene() {
		Arr arr{};
		arr[0] = arr[1] = true;

		primes.push_back(2);
		for(int i = 4; i < N; i += 2) arr[i] = true;
		for(int i = 3; i < N; i += 2) {
			if(arr[i] == false) {
				primes.push_back(i);
				for(int j = i * i; j < N; j += 2 * i)
					arr[j] = true;
			}
		}
	}
};


const int LIM = 1e6 + 5;
eratostene<LIM, std::bitset<LIM>> ciur{};

void solve() {
	long long a, b; std::cin >> a >> b;
	std::vector<int> divizori;

	for(auto p : ciur.primes) {
		if(p * p > b) break;

		if(b % p == 0) divizori.push_back(p);
		while(b % p == 0) b /= p;
	}

	if(b > 1) divizori.push_back(b);

	long long numere = 0;
	const int subsets = 1 << divizori.size();

	for(int i = 1; i < subsets; i++) {
		int sign = -1;
		long long produs = 1;

		for(int pos = 0; pos < divizori.size(); pos++)
			if(((i >> pos) & 1)) {
				sign = -sign;
				produs *= divizori[pos];
			}

		numere += sign * (a / produs);
	}

	std::cout << a - numere << '\n';
}


int main() { 
	std::ios_base::sync_with_stdio(0);
	std::cin.tie(0); std::cout.tie(0);

	freopen("pinex.in", "r", stdin);
	freopen("pinex.out", "w", stdout);

	int t; std::cin >> t; while(t--) {
		solve();	
	}

	return 0;
}