#include<iostream>
#include<fstream>
#include<vector>
using namespace std;
const long MAX = 1000000;


int euclid(int a, int b){
	if (b == 0){
		return a;
	}
	else{
		return euclid(b, a%b);
	}
}





int main(){
	//////////////////////////////////////////
	bool prime[MAX];
	vector<long> prim;
	for (int i = 0; i < MAX; i++){
		prime[i] = true;
	}
	for (int i = 2; i < MAX; i++)
	{
		if (prime[i] == true){
			prim.push_back(i);
			for (int j = i+i; j < MAX; j += i){
				prime[j] = false;;
			}
		}
	}
	////////////////////////////////////////
	ifstream f("pinex.in");
	int n = 0;
	f >> n;
	long a, b;
	ofstream o("pinex.out");
	for (int i = 0; i < n; i++){
		int x = 0;
		f >> a >> b;
		vector<int> divizori;
		for (int i = 0; i <= prim.size(); i++){
			if (prim[i] <= a){
				if (b!=prim[i]&&b%prim[i] == 0){
					divizori.push_back(prim[i]);

				}
			}
			else{
				break;
			}
		}
		x = 0;
		if (divizori.size() > 2 || divizori.size()==0){
			for (int i = 0; i < divizori.size(); i++){
				x += a / divizori[i];
				for (int k = i + 1; k < divizori.size(); k++){
					x -= (a / (divizori[i] * divizori[k]));
				}


			}
			x += a / b;
		}
		else if(divizori.size()==2|| divizori.size()==1){
			for (int i = 0; i < divizori.size(); i++){
				x += a / divizori[i];
				for (int k = i + 1; k < divizori.size(); k++){
					x -= (a / (divizori[i] * divizori[k]));
				}
			}
		}
		

		
		o << a-x << '\n';
	}
	return 0;
}