#include <fstream>
#include <vector>

using namespace std;

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

vector<int> v;

void bkt(long long &sum, int nr, int a, int k = -1, int nrselected = 0, int s = 1) {
	if (k + 1 == v.size()) {
		if (nrselected == nr) {
			sum += a/s;
		}
		return;
	}
	bkt(sum, nr, a, k + 1, nrselected + 1, s * v[k + 1]);
	bkt(sum, nr, a, k + 1, nrselected, s);
}

int main() {
	int m;
	cin >> m;
	while (m--) {
		int a, b; 
		cin >> a >> b;
		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;
		int coef = 1;
		for (int i = 1; i <= v.size(); i++) {
			long long temp = 0;
			bkt(temp, i, a);
			s += coef * temp;
			coef = -coef;
		}
		cout << a - s << '\n';
		while (!v.empty()) {
			v.pop_back();
		}
	}
	return 0;
}