//  InfoArena ~~ Pinex

#include <fstream>
#include <cmath>

using namespace std;

ifstream in("pinex.in");
ofstream out("pinex.out");

const int NMAX  = 1000000;
const int P_MAX = 200000;

long long p[P_MAX+1];   ///  Tin divizorii primi ai lui Y
bool ciur[NMAX+3];
long long pr[P_MAX+1], pr_count= 0;  ///  Tin numerele prime
long long A,B;

void ciurul() {
    long long lim= 1000;
    for( int i= 4;  i<=NMAX;  i+= 2 ) ciur[i]= 1;
    for( int i= 3;  i<=lim;   i+= 2 ) {
        if( !ciur[i] ) {
            for( int j= i*i;  j<=NMAX;  j+= 2*i ) ciur[j]= 1;
        }
    }
    pr[ ++pr_count ]= 2;
    for( int i= 3;  i<=NMAX;  i+= 2 ) {
        if( !ciur[i] )  pr[ ++pr_count ]= i;
    }
}

long long Desc_factori( long long N ) {
    long long R= 0, ind= 1;
    long long lim= (long long)sqrt( 1.0*N );
    bool ok= 0;
    while( N>1 && pr[ind]<=lim ) {
        ok= 0;
        while( N%pr[ind] == 0 ) {
            N/= pr[ind];
            ok= 1;
        }
        if( ok ) {
            p[ ++R ]= pr[ind];
            lim= (long long)sqrt( 1.0*N );
        }
        ++ind;
    }
    if( N>1 ) p[ ++R ]= N;
    return R;
}


long long PINEX( long long X, long long Y ) {
    long long Sol= 0;
    long long nr= Desc_factori( Y );
    long long k= 1<<nr;
    for( long long i= 1;  i<k;  ++i ) {
        long long cnt= 0, prod= 1;
        for( long long j= 0;  j<nr;  ++j ) {
            if( i & (1<<j) ) {
                ++cnt;
                prod*= p[ j+1 ];
            }
        }
        if( cnt%2 == 1 ) {   ///  Adun divizorii
            Sol+= X/prod;
        }
        else {               ///  Scad divizorii
            Sol-= X/prod;
        }
    }
    return X-Sol;
}


int main() {
    ciurul();
    long long T;
    in >> T;
    for( int t= 0;  t<T;  ++t ) {
        in >> A >> B;
        out << PINEX( A, B ) << '\n';
    }
    return 0;
}