#include <algorithm>
#include <fstream>
#include <iostream>
#include <vector>

using namespace std;

const int MAX = 1 << 20;
bool P[MAX];
int primes[MAX];
long long M, A, B;

int main() {
	ifstream cin("pinex.in");
	ofstream cout("pinex.out");
	for (int i = 2; i * i <= MAX; i++) {
		if (P[i] == 0) {
			for (int j = i * i; j < MAX; j += i) {
				P[j] = true;
			}
		}
	}
	for (int i = 2, j = 0; i < MAX; i++) {
		if (P[i] == 0) {
			primes[j++] = i;
		}
	}
	cin >> M;
	while (M--) {
		cin >> A >> B;
		vector<int> div;
		for (int i = 0; 1LL * primes[i] * primes[i] <= B; i++) {
			if (B % primes[i] == 0) {
				div.push_back(primes[i]);
			}
			while (B % primes[i] == 0) {
				B /= primes[i];
			}
		}
		if (B != 1) {
			div.push_back(B);
		}
		int n = div.size();
		int cnt = 0;
		for (int mask = 0; mask < 1 << n; mask++) {
			int p = 1;
			for (int i = 0; i < n; i++) {
				if (mask & (1 << i)) {
					p *= div[i];
				}
			}
			if (__builtin_popcount(mask) & 1) {
				cnt += A / p;
			} else {
				cnt -= A / p;
			}
		}
		cout << abs(cnt) << endl;
	}
	return 0;
}