// sursa asa la sto sa vad cat ia mobius
#include <bits/stdc++.h>

using namespace std;

ifstream fin("pinex.in");
ofstream fout("pinex.out");

const int BMAX = 1e6;

int T;
int mob[BMAX + 1];

void buildMob(int n = BMAX) {
	mob[0] = mob[1] = 1;

	for(int i = 2; i <= n; i++) {
		if(mob[i] == 0) {
			mob[i] = -1;

			for(int j = i + i; j <= n; j += i) {
				if(mob[j] == 0) {
					mob[j] = -1;
				} else {
					mob[j] = -mob[j];
				}
			}
		}
	}

	for(int i = 2; i * i <= n; i++) {
		mob[i * i] = 0;
	}

	for(int i = 1; i <= n; i++) {
		if(mob[i] == 0) {
			for(int j = i + i; j <= n; j += i) {
				mob[j] = 0;
			}
		}
	}
}

void solve() {
	long long A, B;
	fin >> A >> B;

	assert(B <= BMAX);

	long long ans = 0, d = 1;

	while(d * d < B) {
		if(B % d == 0) {
			ans += A / d * mob[d];
			ans += A * d / B * mob[(B / d)];
		}
		d++;
	}

	if(d * d == B) {
		ans += A * d * mob[d];
	}

	fout << ans << '\n';
}

int main() {
	fin >> T;

	buildMob();

	for(int tc = 1; tc <= T; tc++) {
		solve();
	}
	return 0;
}