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

vector<int> primes;

void calc_primes(const int pana_la, vector<int>& v){
	if(pana_la >= 2){
		v.push_back(2); }
	vector<bool> e_prim((pana_la/2)+1, true);
	for(long long i = 3; i <= pana_la; ++i){
		if(e_prim[i/2]){
			v.push_back(i);
			for(long long j = i*i; j < pana_la; j += i){
				e_prim[j/2] = false; } } } }

void find_prime_divisors(long long x, vector<long long>& rez){
	for(auto it = begin(primes); (*it)*(*it) <= x; ++it){
		if(x % *it == 0){
			rez.push_back(*it);
			do{
				x /= *it;
			} while(x % *it == 0); } }
	if(x != 1){
		rez.push_back(x); } }

constexpr int bitcount(const int x, const int rez = 0){
	return (x==0) ? rez : bitcount(x^(x&-x), rez+1); }

long long find_numbers_with_common_divisor_under(const vector<long long>& x, const long long under){
	long long rez = 0;
	for(int config = 1; config < (1<<x.size()); ++config){
		long long number = 1;
		for(int i = 0; i < x.size(); ++i){
			if((config>>i)&1){
				number *= x[i]; } }
		switch(bitcount(config)%2){
		case 0:
			rez -= under/number;
			break;
		case 1:
			rez += under/number;
			break; } }
	return rez; }

long long solve_test(long long a, long long b){
	vector<long long> divs;
	find_prime_divisors(b, divs);
	return a - find_numbers_with_common_divisor_under(divs, a); }

int main(){
	primes.reserve(78498);
	calc_primes(1000000, primes);

	ifstream f("pinex.in");
	ofstream g("pinex.out");
	int t = 0;
	f >> t;
	for(int i = 0; i < t; ++i){
		long long a, b;
		f >> a >> b;
		g << solve_test(a, b) << '\n'; }
	return 0; }