#include <bits/stdc++.h>
#include <fstream>
#include <math.h>
using namespace std;

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

#define ll long long int
#define MAX_P 100000
long long int a,b,m,f[50];
int fprim[80000];
bool prim[100000];
void precalc(){
	
	fill(prim + 2, prim + 100000, 1);
	
	for(int i = 2;i < 100000;i++){
		if(prim[i]){
			for(int j=2*i;j< 100000;j+=i){
				prim[j]=0;
				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;
		}
		if(d==2)d++;
		else d+=2;
	}
	ll sol=a;
	for(int i=1;i<(1<<t);i++){
		ll prod=1, nr=0;
		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(){
in>>m;

for(int i=1;i<=m;i++){
	in >>a>>b;
	solve();
}

}