#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int cmax = 1e6;

bool c[cmax+5];
int prime[cmax+5], nrp;
int dpr[cmax+5], nrd;
bool tk[cmax+5];
ll ans, a , b;

void cioor() {
	c[1] = true;
	for(int i=3; i<=1e3; i+=2)
		if(!c[i])
			for(int j=i*i; j<=1e6; j+=i)
				c[j] = true;
	prime[++nrp] = 2;
	for(int i=3; i<=1e6; i+=2) if(!c[i]) prime[++nrp] = i;
}

void compute() {
	ll prod = 1;
	int fct = -1;
	int cnt = 0;
	for(int i=1; i<=nrd; i++) {
		//cout << dpr[i] << " " << tk[i] << "\n";
		if(tk[i]) {
			cnt++;
			fct = -fct;
			prod = prod * dpr[i];
		}
	}
	//cout << "\n";
	if(cnt) {
		//cout << fct << " " << prod << "\n";
		ans = ans + fct * (a / prod);
	}
	//cout << "\n";
}

void bt(int k) {
	tk[k] = false;
	if(k<nrd) bt(k+1);
	else compute();
	tk[k] = true;
	if(k<nrd) bt(k+1);
	else compute();
}

int main() {
	ifstream f("pinex.in");
	ofstream g("pinex.out");
	
	cioor();
	int n; f >> n;
	for(int cas=1; cas<=n; cas++) {
		f >> a >> b;
		nrd = 0;
		int k = 1;
		while(prime[k]*prime[k]<=b and k<=nrp) {
			if(b%prime[k]==0) dpr[++nrd] = prime[k];
			while(b%prime[k]==0) b/=prime[k];
			k++;
		}
		if(b>1) dpr[++nrd] = b;
		for(int i=1; i<=nrd; i++) tk[i] = false;
		ans = 0;
		bt(1);
		g << a - ans << "\n";
	}
	return 0;
}