//#include <fstream>
//
//using namespace std;
//
//ifstream in("fractii.in");
//ofstream out("fractii.out");
//
//int n;
//
//void init() {
//	in >> n;
//}
//
//void close() {
//	in.close();
//	out.close();
//}
//
//long long fact(int p) {
//	long long r = 1;
//	while (p > 1) {
//		r *= p;
//		--p;
//	}
//	return r;
//}
//
//long long comb(int n, int k) {
//	return(fact(n) / (fact(k) * fact(n - k)));
//}
//
//void rezolvare() {
//	out << comb() << '\n';
//}
//
//int main()
//{
//	init();
//	rezolvare();
//	close();
//}
#include <fstream>
#include <iostream>

using namespace std;

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

int a, b;

int euclid(int n,int m) {
	if (m>0) {
		return euclid(m,n%m);
	}
	return n;
}

void solve() {
	in >> a >> b;
	int neprime = 0;
	for (int i = 1; i < a; ++i) {
		neprime += euclid(i, b) != 1 ? 1 : 0;
	}
	out << (a - neprime)-1<<'\n';
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	int t = 1;
	in >> t;



	while (t--) {
		solve();
	}

}