#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 ;
        }
    }
}
 
long long calc(long long A, long long 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(long long 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-- )
    {
        long long A, B;
 
        fin >> A >> B ;
 
        fout << calc( A, B ) << "\n" ;
    }
 
    return 0 ;
}