#include<fstream>
#include<cmath>
#define lim 1000008
#include<bitset>
using namespace std;


ifstream f("pinex.in");
ofstream g("pinex.out");
int v[20],prim[lim],r,k,t;
long long x[20],SOL,A,B;
bitset<lim>ok;
void ciur () {
	prim[1]=2;
	k=1;
	for(int i=3; i<=lim ; i+=2  ) {

		if(!ok[i]){
			
			prim[++k]=i;
			
			for(int j=2*i;j<=lim;j+=i)
				ok[j]=1;
			
			ok[i]=1;
		}
		
	}
	
}
void descompune () {
	int i;
	r=0;
	long long w=sqrt(B);
	for(i=1; prim[i]<=w&& i<=k && B>1;i++){
		
		if(B%prim[i]==0){
			
			while(B%prim[i]==0)
				B/=prim[i];
			v[++r]=prim[i];
		}
	}
	if(B!=1)
		v[++r]=B;
}
void afis (){
	
	int nr=0;
	long long sol=1;
	for(int i=1;i<=r;i++)
		if(x[i]){
			++nr;
			sol*=v[i];
		}
	if(nr){
		
		if(nr%2)
			SOL+=A/sol;
		else
			SOL-=A/sol;
	}
}
void back (int niv){
	
	if(niv>r){
		afis();
		return;
	}
	for(int i=0;i<=1;++i){
		x[niv]=i;
		back(niv+1);
	}
}
int main () {
	
	f>>t;
	
	ciur();
	while ( t )  {
		SOL=0;
		f>>A>>B;
		descompune();
		back(1);
		g<<A-SOL<<"\n";
		--t;
	}
	
	return 0;
}