#include <stdio.h>
#include <math.h>
#include <algorithm>
#include <string.h>
#include <fstream>
using namespace std;

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

#define ll long long 
#define MAX_P 1000000

ll A,B,M,fact[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){
			fact[++t] = fprim[d];	
			while (B % fprim[d] == 0)
			 B /= fprim[d];
		}
		
		if(fprim[d] > sqrt(B) && B > 1){
			fact[++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 * fact[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;
for(int i=1;i<=M;i++){
	in>>A>>B;
	solve();
}
return 0;
}