// 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 long long BMAX = 1e12;
const int SQRTBMAX = 1e6;

int T;
char mob[SQRTBMAX + 1];
vector<int> primes;

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

	for(int i = 2; i <= n; i++) {
		if(mob[i] == 0) {
			primes.push_back(i);
			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;
			}
		}
	}
}

char mobTrap(long long x) {
	char ret = 1;
	for(int i = 0; (long long) primes[i] * primes[i] <= x; i++) {
		int p = 0;
		while(x % primes[i] == 0) {
			p++;
			x /= primes[i];
		}

		if(p == 1) {
			ret = -ret;
		} else if(p > 1) {
			return 0;
		}
	}

	if(x > 0) {
		if(ret == 0) {
			ret = -1;
		} else {
			ret = -ret;
		}	
	}

	return ret;
}

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

	assert(B <= BMAX);

	long long ans = 0, d = 1, mobB = mobTrap(B);

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

			if((B / d) > SQRTBMAX) {
				if(__gcd(d, (B / d)) == 1 && mob[d] != 0) {
					ans += A / (B / d) * (mobB / mob[d]);
				} else {
					ans += A / (B / d) * mobTrap(B / d);
				}
			} else {
				ans += A / (B / d) * 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;
}