#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;
	//vector<vector<int>> multimi;
	
	int 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;
		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;

		
		o << a-x << endl;
	}
	return 0;
}