#include <bits/stdc++.h>
using namespace std;
ifstream in ("pinex.in") ;
ofstream out ("pinex.out") ;
const int MAXCIUR = 1000005 ;
bitset < MAXCIUR > ciur  ;
vector < int > prim ;
void ciurulet ()
{
        prim.push_back(2) ;
    for ( int  i = 3 ; i <= MAXCIUR ; i ++ )
    if ( !ciur [ i ] && ( i & 1 ) )
    {
        prim.push_back ( i ) ;
        for ( int j = i * 3 ; j <= MAXCIUR ; j += 2 * i ) ciur [ j ] = 1 ;
    }
}
int64_t x , y ;
void divi ( int64_t n )
{
    int64_t i = 0 , j , nr = 0 , p = 1 , sol , t ;
    vector < int > d ;

    while( n != 1 )
    {
        if ( !( n % prim [ i ] ) )
        {
            d.push_back( prim [ i ] ) ;
            while ( !( n % prim [ i ] ) )    n /= prim [ i ] ;
        }

        if ( prim [ i ] * prim [ i ] >= n && n != 1 )
        {
            d.push_back ( n ) ;
            break ;
        }
         i ++ ;
    }

        nr = 0 ;
        t = ( 1 << d.size() ) ;
        sol = x ;
    for ( i = 1 ; i < t ; ++ i , nr = 0 , p = 1 )
    {
        for ( j = 0 ; j < t ; j ++ )
            if ( i & ( 1 << j ) )
            {
                nr ++ ;
                p = 1LL * p * d [ j ] ;
            }
        if ( nr % 2 )   nr = -1 ;
        else            nr = 1 ;
        sol += nr * x / p ;
    }
        out << sol << '\n' ;
}
int main() {
    int n ;
        in >> n ;
        ciurulet() ;
    while ( n -- )
    {
        in >> x >> y ;
        divi ( y ) ;
    }
}