#include <cstdio>

#define MAX_VAL 1000000
#define MAX_P 80000

bool prime[MAX_VAL];
int p[MAX_P], nrp;
int pdiv[30], nrpdiv;
int sol[10];

void ciur() {
    for ( int i = 2; i * i < MAX_VAL; ++i )
        if ( !prime[i] )
            for ( int j = i * i; j < MAX_VAL; j += i )
                prime[j] = true;

    for ( int i = 2; i < MAX_VAL; ++i )
        if ( !prime[i] )
            p[nrp++] = i;
}

void desc( long long x ) {
    nrpdiv = 0;
    int i = 0;
    while ( i < nrp && ( long long ) p[i] * p[i] <= x ) {
        if ( x % p[i] == 0 ) {
            pdiv[nrpdiv++] = p[i];

            while ( x % p[i] == 0 )
                x /= p[i];
        }
        ++i;
    }
    if ( x > 1 )
        pdiv[nrpdiv++] = x;
}

void compute( int n, int a, long long &res ) {
    int count = 0;
    long long prod = 1;
    for ( int i = 0; i < n; ++i )
        if ( sol[i] ) {
            ++count;
            prod *= pdiv[i];
        }

    if ( count & 1 )
        count = -1;
    else
        count = 1;

    res += ( long long ) count * a / prod;
}

void bkt( int pos, int n, int a, long long &res ) {
    if ( pos == n )
        compute( n, a, res );
    else
        for ( int i = 0; i < 2; ++i ) {
            sol[pos] = i;
            bkt( pos + 1, n, a, res );
        }
}

int main() {
    FILE *fin, *fout;

    ciur();

    fin = fopen( "pinex.in", "r" );
    int q;
    fscanf( fin, "%d", &q );
    fout = fopen( "pinex.out", "w" );
    while ( q ) {
        long long a, b;
        fscanf( fin, "%lld%lld", &a, &b );
        
        desc( b );
        
        long long res = 0;
        bkt( 0, nrpdiv, a, res );

        fprintf( fout, "%lld\n", res );

        --q;
    }

    fclose( fin );
    fclose( fout );
}