# include <cstdio>
# include <cmath>

typedef long long ll ;
const char *FIN = "pinex.in", *FOU = "pinex.out" ;
const int BMAX = 1000000, MAX = 1 << 17 ;

ll A, B, put[30] ;
int T, P[BMAX - 920000] ;
unsigned char V[MAX] ;

void prec ( void ) {
    P[ ++P[0] ] = 2 ;

    for (int i = 1; ( i * i << 1 ) + ( i << 1 ) < BMAX; ++i) {
        if ( ( V[i >> 3] & ( 1 << ( i & 7 ) ) ) ) continue;
        for (int j = ( i * i << 1 ) + ( i << 1 ); ( j << 1 ) + 1 < BMAX; j += ( i << 1 ) + 1) {
            V[j >> 3] |= 1 << ( j & 7 ) ;
        }
    }
    for (int i = 1; ( i << 1 ) + 1 < BMAX; ++i) {
        if ( ( V[i >> 3] & ( 1 << ( i & 7 ) ) ) == 0 ) {
            P[ ++P[0] ] = ( i << 1 ) + 1 ;
        }
    }
}

int fact ( ll N ) {
    int k = 0;

    for (int i = 1; 1LL * P[i] * P[i] <= N ; ++i)
        if (N % P[i] == 0) {
            for (put[++k] = P[i] ; N % P[i] == 0; N /= P[i]) ;
        }
    if (N > 1)
        put[++k] = N;

    return k ;
}

void solve ( ll A, ll B ) {
    int k = fact ( B ) ;

    ll sol = A ;

    for (int i = 1; i < 1 << k; ++i) {
        ll nr_mul = 0, elem = 1;
        for (int j = 0; j < k; ++j)
            if ( i & 1 << j )
                elem *= 1LL * put[k - j], ++nr_mul ;

        nr_mul = nr_mul & 1 ? -1 : 1 ;

        sol += 1LL * nr_mul * A / elem ;
    }

    printf ( "%lld\n", sol ) ;
}

int main ( void ) {

    freopen ( FIN, "r", stdin ) ;
    freopen ( FOU, "w", stdout ) ;

    prec () ;
    for ( scanf ( "%d", &T ); T ; --T ) {
        scanf ( "%lld %lld", &A, &B ) ;
        solve ( A , B ) ;
    }
}