#include <vector>
#include <fstream>
#include <cstdlib>
#define N_MAX 70011

using namespace std;
char isPrime[N_MAX];
vector< int > PrimeNr;
void Sieve( void )
{
    int i, j, pas;
    for( i=1; ((i*i)<<1)+(i<<1) < 110000 ; ++i )
        if( 0 == ( isPrime[i>>3] & (1<<(i&7)) ) )
        {
            pas=(i<<1)+1;
            for( j=((i*i)<<1)+(i<<1); j<<1 < 1100000; j+=pas )
                isPrime[j>>3]|=1<<(j&7);
        }
    PrimeNr.push_back(2);
    for( i=3, j=1; i < 1100000; i+=2, ++j )
       if( 0 == ( isPrime[j>>3] & (1<<(j&7)) ) )
         PrimeNr.push_back(i);
}
int main( void )
{
	int M, _count;
	long long int A, B,	i, j, s, till, p;
	Sieve();
	ifstream in( "pinex.in" );
	ofstream out( "pinex.out" );
	for( in>>M; M; --M )
	{
		in>>A>>B;
		vector< int > isDivB;
		for( i=0; 1LL*PrimeNr[i]*PrimeNr[i] <= B; ++i )
			if( 0 == B%PrimeNr[i] )
			{
				isDivB.push_back(PrimeNr[i]);
				for( ; 0 == B%PrimeNr[i]; B/=PrimeNr[i] );
			}
		if( B > 1 )
			isDivB.push_back(B);
		till=1<<(isDivB.size());
		for( i=1, s=0; i < till; ++i )
		{
			for( p=1, _count=j=0; (1<<j) <= i; ++j )
				if( i&(1<<j) )
				{
					++_count;
					p*=isDivB[j];
					if( p > A )
						break;
				}
			if( (1<<j) <= i )
				continue;
			if( 0 == _count%2 )
				p*=-1;
			s+=A/p;
		}
		out<<(A-s)<<'\n';
	}
	return EXIT_SUCCESS;
}