#include <algorithm>
#include <bitset>
#include <cmath>
using namespace std;

#define MAX_PRIM 80005
#define MAX_SQRT_B 1000005

typedef int int_32;
typedef long long int int_64;

int_32 T;
int_32 fact[ MAX_PRIM ], prim[ MAX_PRIM ];
int_64 A, B, XXX;
bitset <MAX_SQRT_B> f;

void ciur() {

    int_32 i, j;

    f.set();
    f[ 0 ] = f[ 1 ] = false;

    for( i = 2; i <= MAX_SQRT_B; ++i )
        if( f[ i ] == true ) {

            prim[ ++prim[ 0 ] ] = i;
            for( j = 2*i; j <= MAX_SQRT_B; j += i )
                f[ j ] = false;
        }
}

void solve() {

    int_32 j, cnt, semn;
    int_64 i, prod, lim_sup;

    XXX = 0;
    memset( fact, 0, sizeof( fact ) );

    scanf( "%lld %lld", &A, &B );

    cnt = 0;
    while( B > 1 ) {

        ++cnt;
        if( B % prim[ cnt ] == 0 ) {

            fact[ ++fact[ 0 ] ] = prim[ cnt ];
            while( B % prim[ cnt ] == 0 )
                B /= prim[ cnt ];
        }

        if( prim[ cnt ] > sqrt( B ) && B > 1 ) {

            fact[ ++fact[ 0 ] ] = B;
            break;
        }
    }

    lim_sup = 1 << fact[ 0 ];
    for( i = 1; i < lim_sup; ++i ) {

        cnt = 0;
        prod = 1;
        for( j = 1; j <= fact[ 0 ]; ++j )
            if( i & ( 1 << (j-1) ) ) {

                prod *= fact[ j ];
                ++cnt;
            }

        if( cnt & 1 )
            semn = 1;
        else
            semn = -1;

        XXX += (int_64)semn * A/prod;
    }

    printf( "%lld\n", A - XXX );
}

int main() {

    freopen( "pinex.in", "r", stdin );
    freopen( "pinex.out", "w", stdout );

    ciur();

    scanf( "%d", &T );
    while( T-- )
        solve();

    return 0;
}