#include <fstream>
#include <vector>
#include <bitset>

using namespace std;

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

vector<unsigned> prime_divisors;
vector<unsigned> primes;
bitset<1000005> ciur_a_censored;

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

void ciur_maker() {
	ciur_a_censored[0] = ciur_a_censored[1] = 1;
	for (unsigned i = 2; i <= 1000000; i++)
		if (!ciur_a_censored[i]) {
			primes.emplace_back(i);
			for (unsigned j = i * i; j <= 1000000; j += i)
				ciur_a_censored[j] = 1;
		}
}

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

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

	for (unsigned j = 1; j <= queries; j++) {
		unsigned long long number_to_consider;
		cin >> up_limit >> number_to_consider;

		unsigned long long factor = 2;
		for (unsigned long long i = 0; primes[i] * primes[i] <= number_to_consider && i < primes.size(); i++) {
			unsigned current_primes_de_i = primes[i];
			if (!(number_to_consider % primes[i])) {
				prime_divisors.emplace_back(primes[i]);
				do
					number_to_consider /= primes[i];
				while (!(number_to_consider % primes[i]));
			}
		}
		if (number_to_consider != 1)
			prime_divisors.emplace_back(number_to_consider);

		long long 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();
	}
}