#include<fstream>
#include<math.h>
#define val 1000010

using namespace std;

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

bool V[val];
int i,k,nr,semn,p,Prim[100010],T,j;
long long A,B,divizori[20],prod,total;
double rad;


int main(){
	
	f>>T;
	Prim[++k]=2;
	for(i=3;i<=val;i+=2){
		if(V[i]==0){
			Prim[++k]=i;
			for(j=i;j<=val;j+=i)
				V[j]=1;
		}
	}
	
	while(T--){
		f>>A>>B;
		nr=0;total=0;
		rad=sqrt(B);
		for(i=1;i<=k&&(Prim[i]<=rad);i++){
			if(B%Prim[i]==0){
				divizori[++nr]=Prim[i];
				while((B%Prim[i])==0)
					B/=Prim[i];
			}
		}
		if(B!=1)
			divizori[++nr]=B;
		p=1;
		while( p!=(1<<(nr)) ){
			semn=0;prod=1;
			for(i=0;i<nr;i++){
				if((p&(1<<i))!=0){
					semn++;
					prod*=divizori[i+1];
				}
			}
			if(semn%2==1)
				total+=A/prod;
			else
				total-=A/prod;
			p+=1;
		}
		g<<A-total<<"\n";
	}
	
	return 0;
}