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

#define MAX_P 1000005 
long long primes[MAX_P], fact[MAX_P/10];
bool isPrime[MAX_P];

void fillPrimes(){
	fill(isPrime+2,isPrime+MAX_P,1);
	for(int i=2; i<MAX_P; i++) 
	   if(isPrime[i]){
	      //if(i*i>0) 
	        for(int j=2*i; j<MAX_P; j=j+i)
	          isPrime[j]=false;
		  primes[++primes[0]]=i;	  
		}
}

int main(){
	fillPrimes();
	ifstream in("pinex.in");
	FILE *out=fopen("pinex.out","w");
	int m;
	long long a, b, i,noDiv, sol;
	in>>m;
	
	while(m--){
		in>>a>>b; 
		
		i=0; noDiv=0; sol=0;
		while(b>1){
			i++; 
			if(b%primes[i]==0){
				fact[++noDiv]=primes[i];
				while(b%primes[i]==0 && b>1)
				     b=b/primes[i];
			}
			if(primes[i]>sqrt(b) && b>1){
				fact[++noDiv]=b;
				b=1;
			}
		}
		
		for(i=1;i<(1<<noDiv);i++){
			long long nr=0, prod=1;
			for(int j=0;j<noDiv;j++)
			   if((1<<j)&i){
			   	   nr++;
			   	   prod*=1LL*fact[j+1];
			   }
			 if(nr%2==0) prod*=-1;
			 sol+=1LL*a/prod;  
		}
		fprintf(out,"%lld\n",a-sol);
	}
	
	
	in.close(); fclose(out);
	return 0;
}