#include <vector>
#include <cstdlib>
#include <fstream>
#define MAX_N  1000003

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