#include <cstdio>
#include <bitset>
#include <vector>
using namespace std;

const int NMAX = 1000505;

int tests;
long long A, B;
bitset<NMAX> notPrime;
vector<int> primes;

void precomputePrimes() {
	for (int i = 2; i * i < NMAX; i++) {
		if (!notPrime[i]) {
			for (int j = i * i; j < NMAX; j += i) {
				notPrime[j] = 1;
			}
		}
	}

	for (int i = 2; i < NMAX; i++) {
		if (!notPrime[i]) {
			primes.push_back(i);
		}
	}
}

vector<long long> decompose(long long number) {
	vector<long long> primeDivisors;

	for (int j = 0; j < primes.size() && 1LL * primes[j] * primes[j] <= number; j++) {
		if (number % primes[j] == 0) {
			primeDivisors.push_back(primes[j]);
			while (number % primes[j] == 0) {
			 	number /= primes[j];
			}
		}
	}

	if (number != 1) {
		primeDivisors.push_back(number);
	}

	return primeDivisors;
}

long long count(long long N, vector<long long>& primeFactors) {
	int totalSize = primeFactors.size();
	long long result = 0;

	for (int mask = 1; mask < (1 << totalSize); mask++) {
		int cntFactors = 0;
		long long productFactorsInMask = 1;
		for (int factorIdx = 0; factorIdx < totalSize; factorIdx++) {
			if (mask & (1 << factorIdx)) {
				cntFactors++;
				productFactorsInMask *= primeFactors[factorIdx];
			}
		}

		int sign = (cntFactors & 1) ? 1 : -1;
		result += 1LL * sign * (N / productFactorsInMask);
	}

	return result;
}

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

	precomputePrimes();
	scanf("%d", &tests);
	for (int test_no = 0; test_no < tests; test_no++) {
		scanf("%lld%lld", &A, &B);
		vector<long long> primeFactors = decompose(B);
		printf("%lld\n", A - count(A, primeFactors));
	}

	return 0;
}