#include<stdio.h>
#include<bitset>

#define maxPr 78501
#define maxB 1000001

using namespace std;

FILE*f=fopen("pinex.in","r");
FILE*g=fopen("pinex.out","w");

int m,nrpr,Pr[maxPr];
int i,X[50]; long long A,B;
int nrf; long long R,F[50];
bitset<maxB+5>ciur;

inline void Ciur () {
	
	Pr[++nrpr] = 2; ciur[2] = 1;
	
	for ( int i = 3 ; i <= maxB ; i += 2 ){
		if ( !ciur[i] ){
			
			Pr[++nrpr] = i;
			
			for ( int j = i + i + i ; j <= maxB ; j += i + i ){
				ciur[j] = 1;
			}
			
		}
	}
	
}

inline void descompune () {
	
	nrf = 0;
	
	for ( int i = 1 ; i <= nrpr && B > 1 && 1LL * Pr[i] * Pr[i] <= B ; ++i ){
		
		if ( !(B % Pr[i]) ){
			++nrf; F[nrf] = Pr[i];
			
			while ( !(B % Pr[i]) ){
				B /= Pr[i];
			}
		}
		
	}
	
	if ( B > 1 ){
		++nrf; F[nrf] = B;
	}
}

inline void Solutie () {
	
	long long prod = 1; int nr = 0;
	
	for ( int i = 1 ; i <= nrf ; ++i ){
		
		if ( X[i] ){
			prod = prod * F[i];
			++nr;
		}
		
	}
	
	if ( !nr ) return ;
	
	if ( nr & 1 ){
		R += A / prod;
	}
	else{
		R -= A / prod;
	}
	
}


void back ( int niv ){
	
	if ( niv == nrf + 1 ){
		Solutie();
		return ;
	}
	
	for ( int i = 0 ; i <= 1 ; ++i ){
		X[niv] = i;
		back(niv+1);
	}
	
}


int main () {
	
	fscanf(f,"%d",&m);
	
	Ciur();
	
	for ( i = 1 ; i <= m ; ++i ){
		fscanf(f,"%lld %lld",&A,&B);
		
		R = 0;
		descompune();
		back(1);
		
		fprintf(g,"%lld\n",A - R);
	}
	
	fclose(f);
	fclose(g);
	
	return 0;
}