#include <bits/stdc++.h>
#include <fstream>

using namespace std;

ifstream in("pinex.in");
ofstream out("pinex.out");

#define ll long long
#define MAX_P 100000
ll m,a,b,f[30];
int fprim[80000];
bool prim[MAX_P];

void prec() {

    
	fill(prim + 2, prim + MAX_P, 1);
 
	for (int i = 2; i < MAX_P; i++)
		if (prim[i]) {
			for (int j = 2 * i; j < MAX_P; j += i)
				prim[j] = false;
			fprim[++fprim[0]] = i;
		}
}

void solve(){
	ll t=0, d=0;
	while(b>1){
		d++;
		if(b % fprim[d] == 0){
			f[++t]=fprim[d];
		while(b % fprim[d] == 0)
			b /= fprim[d];	
		}
		if(fprim[d]> sqrt(b) && b>1){
			f[++t]=b;
			b=1;
		}
	
	}
	
	ll sol=a;
	for(int i=1;i < (1<<t);i++){
		ll nr=0, prod=1;
		for(int j=0;j<t;j++)
			if((1<<j) & i){
				prod=1ll * prod * f[j+1];
				nr++;
			}
		
		if(nr % 2)nr=-1;
		else nr=1;
		
		sol = sol + 1ll * nr * a / prod;
	}
	out<<sol<<"\n";
}

int main(){
	prec();
in>>m;
while(m--){
in >>a>>b;
	solve();
}

}