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

using namespace std;

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

#define ll long long

ll m,a,b,f[30];

void solve(){
	ll t=0, d=2;
	while(b>1){
		if(b % d == 0){
			f[++t]=d;
		while(b % d == 0)
			b/=d;	
		}
		if(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 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(){
in>>m;
while(m--){
in >>a>>b;
	solve();
}

}