/*
 * Code by Spiromanul
 */

# include "fstream"
# include "cstring"
# include "vector"
# include "queue"
# include "bitset"
# include "algorithm"
# include "map"
# include "deque"
# include "iomanip"
# include "cmath"

const char IN [ ] =  "pinex.in" ;
const char OUT [ ] = "pinex.out" ;
const int MAX = 1000014 ;

# define pb push_back
# define mp make_pair
# define FORN( a , b , c ) for ( int a = b ; a <= c ; ++ a )
# define FORNBACK( a , b , c ) for ( int a = b ; a >= c ; -- a )

using namespace std;

ifstream cin ( IN ) ;
ofstream cout ( OUT ) ;

bitset < MAX > viz ;

long long prime [ MAX ] ; int np ;
long long fact [ MAX ] ; int facts ;

inline void ciur ( )
{
    for ( int i = 2 ; i * i <= 1000000 ; ++ i )
        if ( viz [ i ] == 0 )
            for ( int j = i * i ; j <= 1000000 ; j += i )
                viz [ j ] = 1 ;
    FORN ( i , 2 , 1000000 ) if ( viz [ i ] == 0 )
        prime [ ++ np ] = i ;
}

inline long long solve ( long long A , long long B )
{
    int d = 1 ; facts = 0 ;
    while ( d <= np and prime [ d ] * prime [ d ] <= B )
    {
        int ok = 0 ;
        while ( B % prime [ d ] == 0 )
        {
            B /= prime [ d ] ;
            ok = 1 ;
        }
        if ( ok )
            fact [ ++ facts ] = prime [ d ] ;
        ++ d ;
    }
    if ( B > 1 )
        fact [ ++ facts ] = B ;

    long long CET = A ;

    FORN ( i , 1 , -1 + ( 1 << facts ) )
    {
        int number = 0 ;
        long long aux = 1 ;
        FORN ( j , 0 , facts - 1 )
        {
            if ( i & ( 1 << j ) )
            {
                ++ number ;
                aux = aux * fact [ j + 1 ] ;
            }
        }
        if ( number & 1 )
            aux = - aux ;
        CET = CET + A / aux ;
    }

    return CET ;
}

int main ( void )
{
    ciur ( ) ;
    int t ;
    cin >> t ;
    FORN ( i , 1 , t )
    {
        long long A , B ;
        cin >> A >> B ;
        cout << solve ( A , B ) << '\n' ;
    }
    return 0;
}