#include <fstream>
#include <bitset>
using namespace std;
ofstream fout ("pinex.out");
ifstream fin ("pinex.in");
bitset <1000001> prim;
int diviz[1000001],divizb[25],pozdiv,t,poz;
long long a,b;
void ciur()
{
    prim[ 1 ] = 1;
    for( int i = 2 ; i <= 1000000 ; i ++ )
    {
        if( prim[ i ] == 0 )
        {
            for( int j = i * 2 ; j <= 1000000 ; j += i )
                prim[ j ] = 1;
        }
    }
    poz = 0;
    for( int i = 2 ; i <= 1000000 ; i++ )
        if( prim[ i ] == 0 )
            diviz[ ++poz ] = i;
}
void solve( long long a , long long b )
{
    pozdiv = 0;
    long long rsp = 0;
    for( int i = 1 ; i <= poz ; i++ )
    {
        if( b % diviz[ i ] == 0 )
        {
            divizb[ ++pozdiv ] = diviz[ i ];
            while( b % diviz[ i ] == 0 )
                b /= diviz[ i ];
        }
    }
    if( b != 1 )
        divizb[ ++pozdiv ] = b;
    for( int i = 1 ; i < ( 1 << pozdiv ) ; i++ )
    {
        long long produs = 1;
        int nrdiv = 0;
        for( int j = 0 ; j < pozdiv ; j++ )
        {
            if( i & ( 1 << j ) )
            {
                nrdiv++;
                produs *= divizb[ j + 1 ];
            }
        }
        if( nrdiv % 2 )
            rsp += a / produs;
        else
            rsp -= a / produs;
    }
    fout<<a - rsp<<'\n';
}
int main()
{
    fin>>t;
    ciur();
    while( t-- )
    {
        fin>>a>>b;
        solve( a , b );
    }
}