#include <fstream>
#include <vector>
using namespace std;

inline int nr_biti(long long a) {
	int nr_biti = 0;
	while(a != 0) {
		++nr_biti;
		a &= a - 1;
	}
	return nr_biti;
}

int solve(long long a, long long b) {
	vector <int> prime;
	long nr = b;
	if(nr % 2 == 0)
		prime.push_back(2);
	while(nr % 2 == 0) nr /= 2;
	for(int i = 3; nr != 1; i += 2) 
		if(nr % i == 0) {
			prime.push_back(i);
			while(nr % i == 0)
				nr /= i;
		}
	
	int sum = a;
	for(long long i = 1; i < (1LL << prime.size()); ++i) {
		long long prod = (nr_biti(i) % 2 == 1 ? -1 : 1);
		for(int j = 0; (1LL << j) <= i; ++j)
			if(((1LL << j) & i) != 0)
				prod *= prime[j];
		sum += a / prod;
	}
	return sum;
}

int main(void) {
	int n;
	long long a, b;
	ifstream fin("pinex.in");
	ofstream fout("pinex.out");
	fin >> n;
	for(int i = 0; i < n; ++i) {
		fin >> a >> b;
		fout << solve(a, b) << '\n';
	}
	fin.close();
	fout.close();
}