#include<fstream>
#include<bitset>
#include<vector>
using namespace std ;

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

#define maxn 1000001
#define maxp 300000

int tst ;

//bitset<maxn> ok ;
char ok[maxn];

int prim[maxp], nrp ;

vector<int> factori ;

void ciur()
{
    for(int i = 2; i < maxn; ++i )
    {
        if( ok[i] == 0 )
        {
            prim[ ++nrp ] = i ;

            for(long long j = ( long long )i * i ; j < maxn; j +=i )
                ok[j] = 1 ;
        }
    }
}

int calc(int A, int B)
{
    long long sol = A ;

    factori.clear() ;

    for(int i = 1; i <= nrp, ( long long ) prim[i] * prim[i] < B; ++i )
    {
        if( B == 1 )
            break ;

        if( B % prim[i] == 0 )
        {
            factori.push_back( prim[i] ) ;

            while( B % prim[i] == 0 )
                B /= prim[i] ;
        }
    }

    if( B > 1 )
        factori.push_back( B ) ;

    int nrf = factori.size() ;

    for(int i = 1; i < ( 1 << nrf ); ++i )
    {
        long long semn = 0, prod = 1 ;

        for(int j = 0; j < nrf; ++j )
        {
            if( ( 1 << j ) & i )
            {
                prod = ( long long ) prod * factori[j] ;
                ++semn ;
            }
        }

        if( semn % 2 )
            semn = -1 ;
        else
            semn = 1 ;

        sol = sol + ( long long ) semn * A / prod ;
    }

    return sol ;
}

int main()
{
    ciur() ;

    fin >> tst ;

    while( tst-- )
    {
        int A, B;

        fin >> A >> B ;

        fout << calc( A, B ) << "\n" ;
    }

    return 0 ;
}