#include <fstream>
#include <vector>

using namespace std;

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

vector<unsigned long long> prime_divisors;

unsigned long long divider = 1;
unsigned long long up_limit;

void create_reunions(unsigned long long start_pos, unsigned long long max_size, int &solutions, unsigned long long length) {
	for (unsigned long long pos = start_pos; pos < prime_divisors.size(); pos++) {
		divider *= prime_divisors[pos];
		if (start_pos < max_size - 1)
			create_reunions(pos + 1, max_size, solutions, length + 1);
		else if (length == max_size)
			solutions += (up_limit / divider) * (max_size % 2 ? 1 : -1);
		divider /= prime_divisors[pos];
	}
}

int main() {
	unsigned long long queries;
	cin >> queries;

	while (queries--) {
		unsigned long long number_to_consider;
		cin >> up_limit >> number_to_consider;

		unsigned long long factor = 2;
		while (factor * factor <= number_to_consider) {
			bool divisible = 0;
			while (number_to_consider % factor == 0)
				number_to_consider /= factor, divisible = 1;
			if (divisible)
				prime_divisors.emplace_back(factor);
			factor % 2 ? factor += 2 : factor++;
		}
		if (number_to_consider != 1 || !prime_divisors.size())
			prime_divisors.emplace_back(number_to_consider);

		int solutions = 0;
		for (unsigned long long i = 1; i <= prime_divisors.size(); i++)
			create_reunions(0, i, solutions, 1);

		cout << up_limit - solutions << "\n";

		prime_divisors.clear();
	}
}