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

const int MAXP = 1e6 + 5;
bool comp[MAXP];
vector<long long> primes;

vector<long long> factors(long long b);

long long query(long long a, long long b){
	long long code, k, product, sum, parity;
	vector<long long> fact = factors(b);

	sum = 0;
	for(long long i = 1; i <= (1 << fact.size()) - 1; ++i){ //iterates through all subsets;
		code = i;
		k = 0;
		product = 1;
		parity = 1;
		while(code != 0){
			if(code % 2 == 1){
				//cout << *(fact.begin() + k) << " ";
				product *= *(fact.begin() + k);
				parity *= -1;
			}
			code = code >> 1;
			++k;
		}
		sum += parity * (a / product);
		//cout << "\n";
	}
	return a + sum;
}

vector<long long> factors(long long b){
	vector<long long> factor_list;
	for(auto p : primes){
		if(p*p > b)
			break;

		if(b % p == 0)
			factor_list.push_back(p);

		while(b % p == 0)
			b = b / p;

	}
	if(b != 1)
		factor_list.push_back(b);

	return factor_list;
}

void erathostenes(){
	int p = 2;
	while(p*p <= MAXP){
		for(int i = 2*p; i <= MAXP; i = i + p){
			comp[i] = true;
		}
		++p;
		while(comp[p])
			++p;
	}

	for(int i = 2; i <= MAXP; ++i){
		if(!comp[i])
			primes.push_back(i);
	}
}


int main(){
	ifstream fin;
	ofstream fout;
	fin.open("pinex.in");
	fout.open("pinex.out"); 
	long long n, a, b;

	fin >> n;
	erathostenes();
	for(int i=1; i<=n; ++i){
		fin >> a >> b;
		fout << query(a, b);
		fout << "\n";
	}

}