#include<fstream.h>
#include <math.h>

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

long long id,i,j,M,A,B,R;
bool pr[ 500005 ];
int pr2[ 500005 ],fact[ 1000 ],nrpr,nrf;


void ciur()
{
	pr2[ 0 ]=2; nrpr=0; // pr[i]= daca 2*i+1 e prim
	for ( i = 1 ; i <= 500000 ; i++ ) // pr2[i]=al (i+1)-lea nr prim
	{
		if( !pr[ i ] )
		{
			pr2[ ++nrpr ]=2*i+1;
			for( j = 2 * i * i + 2 * i ; j <= 500000 ; j += 2 * i + 1 )
				pr[ j ] = true;
		}
	}
}

void factori()
{
	i = -1; double L = sqrt( B ); nrf = 0;
	while( B > 1 )  // descompun B in factori primi
	{           // fact[i]=al i-lea factor prim in descompunerea lui B
		i++;    // nrf = numarul factorilor
		if(B % pr2[ i ] == 0)
		{
			fact[ ++nrf ] = pr2[ i ];
			while( B % pr2[ i ] == 0 )
				B /= pr2[ i ];
		}
		if( B > 1 && pr2[ i ] > L ) // daca gasesc divizor mai mare ca sqrt(B)
		{                   // ma opresc pentru ca e ultimul
			fact[ ++nrf ] = B;
			B = 1;
		}
	}
}

void rez()
{
	int nrs=( 1 << nrf ) - 1, nr; // nrs = numarul de ?combinari? intre factori = 2^nrf-1
							//     = numarul de intersectii (submultimi)
	long long prod;         // prod= produsul factorilor luati in considerare
	for ( i = 1 ; i <= (long long)nrs ; i++ )              // in momentul respectiv
	{
		prod = 1; nr = 0;  // nr = numarul de multimi Ai intersectate
							  // in momentul respectiv
		for ( j = 0 ; j < nrf ; j++ )
			if ( i & ( 1 << j ) ) // daca i are bitul j = 1
				// Adica, de ex:
				// Cand i ia valorile 2^j(0<=j<nrf) atunci are un singur bit
				// egal cu 1, deci se vor lua submultimile de cate un element.
				// Submultimea a 2^i-a va fi formata din { fact[nrf-i] }
				// Apoi sunt luate submultimile 2^i+1<2^(i+1), apoi 2^i+2<2^(i+1) etc.
				// Ultima submultime e 2^nrf-1 care are toti bitii 1 si, deci, contine
				// toti factorii.
				// Submultimile nu se calculeaza in ordinea numarului de elemente.
			{
				prod = prod * (long long)fact[ nrf - j ];
				nr++;
			}
		if ( nr & 1) // <=> nr%2 <=> daca nr e impar
			R += (long long)A / prod; // (-1)^(nr-1) = +1
		else
			R -=(long long)A / prod; // (-1)^(nr-1)= -1
	} 
}

int main()
{
	ciur();
	f>>M;
	for(id=1;id<=M;id++)
	{
		//scanf("%lld %lld",&A,&B);
		f>>A>>B;
		R=0;
		factori();
		rez();
		//printf("%lld\n",(long long)A-R);
		g<<(long long)A-R<<"\n";
	}
	
	
}