#include <fstream>
#include <vector>
#define int long long

using namespace std;

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

int32_t main() {
	int m;
	cin >> m;
	while (m--) {
		int a, b;
		cin >> a >> b;
		vector<int> v;
		for (int i = 2; b != 1; i++) {
			if (b % i == 0) {
				v.push_back(i);
				while (b % i == 0) {
					b /= i;
				}
			}
		}
		long long s = 0;
		for (int j = 1; j < (1 << v.size()); j++) {
			long long temp = 1;
			int aa = j, it = -1;
			int coef = -1;
			while (aa) {
				it++;
				if (aa & 1) {
					temp *= v[it];
					coef = -coef;
				}
				aa >>= 1;
			}
			s += coef * (a / temp);
		}
		cout << a - s << '\n';
		while (!v.empty()) {
			v.pop_back();
		}
	}
	return 0;
}