#include <iostream>
#include <fstream>

using namespace std;

ifstream fin ("pinex.in") ;
ofstream fout ("pinex.out") ;

const int Vmax = 1e6 ;

bool ciur[Vmax + 1] ;
long long fact[200] ;
int nrFactors ;
long long primes[80000] ;
int P ;

void gen_ciur ()
{
    for ( int i = 2; i <= Vmax; ++ i )
        ciur[i] = true;

    for ( int i = 4; i <= Vmax; i += 2 )
        ciur[i] = false;

    primes[ ++ P] = 2;

    for (int i = 3; i <= Vmax; i += 2 )
        if ( ciur[i] )
        {
            primes[++ P] = i;

            for (int j = 3 * i; j <= Vmax; j += 2 * i)
                ciur[j] = false;
        }
}

void decompose ( long long N )
{
    nrFactors = 0;

    for ( int i = 1 ; 1LL * primes[i] * primes[i] <= N && i <= P ; ++ i)
    {
        if ( N % primes[i] != 0 )
                continue ;

        while ( N % primes[i] == 0 )
               N /= primes[i] ;

        fact [ nrFactors++ ] = primes[i];
    }

    if (N > 1)
        fact[ nrFactors ++ ] = N;
}

long long pinex ( long long A )
{
    long long sol = 0 ;

    for ( int i = 1 ; i < ( 1 << nrFactors ) ; ++ i )  // Ex : 3 factori primi => Adun la 001 , 010 , 100 ; Scad la 011 , 101 , 110 ;
                                                                            //    Adun la 111 .. Astfel imit Pricinpiul
    {
        int nrb = 0;
        long long prod = 1;

        for ( int j = 0 ; j < nrFactors ; ++ j )
            if ( i & ( 1 << j ) )
            {
                ++ nrb ; // nr de biti de 1
                prod *= 1LL * fact[j] ;
            }

        if ( nrb & 1 )
            sol += A / prod ; // numar impar => adun
        else
            sol -= A / prod ; // numar par => scad
    }

    return sol;
}

int main()
{
    gen_ciur() ;

    int M ;
    long long A , B ;

    fin >> M ;

    while ( M -- )
    {
        fin >> A >> B ;
        decompose ( B ) ; // desc in factori primi
        fout << A - pinex(A) << "\n" ;
    }

    return 0;
}