#include <cmath>
#include <cstdio>
#include <iostream>
#include <vector>

using namespace std;

vector <int> primes;

void comp_primes() {
	int i, j, mmax = 1000001;
	vector <bool> notprime(mmax);
	
	primes.push_back(2);
	for (i = 2; i < mmax; i += 2) {
		notprime[i] = 1;
	}
	for (i = 3; i * i < mmax; i += 2) {
		if (!notprime[i]) {
			primes.push_back(i);
			for (j = i * i; j < mmax; j += i) {
				notprime[i] = 1;
			}
		}
	}
}

void solve() {
	vector <int> prime_fact;
	long long A, B, ans = 0;
	int i, mask;
	scanf("%lld %lld", &A, &B);
	
	for (auto x: primes) {
		if (B % x == 0) {
			prime_fact.push_back(x);
			while (B % x == 0) {
				B /= x;
			}
		}
		if (B > 1 && x > sqrt(B)) {
			prime_fact.push_back(B);
			break;
		}

		if (B == 1) {
			break;
		}
	}
	
	for (mask = (1 << prime_fact.size()) - 1; mask; --mask) {
		long long p = 1;
		int cnt = 0;
		for (i = 0; (1 << i) <= mask; ++i) {
			if (mask & (1 << i)) {
				++cnt;
				p *= prime_fact[i];
			}
		}
		if (cnt % 2) {
			ans += A / p;
		}
		else {
			ans -= A / p;
		}
	}
	
	cout << A - ans << '\n';
}

int main() {
	
	freopen("pinex.in", "r", stdin);
	freopen("pinex.out", "w", stdout);
	int t, i;
	
	comp_primes();
	scanf("%d", &t);
	while(t--) {
		solve();
	}
	return 0;
}