#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];

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 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();
}

}