//  InfoArena ~~ Pinex

#include <fstream>

using namespace std;

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

const int P_MAX = 20;

int p[P_MAX+1];   ///  Tin divizorii primi ai lui Y

long long A,B;

int Desc_factori( int N ) {
    int ind= 2, R= 0;
    while( N > 1 ) {
        int cnt= 0;

        while( N%ind == 0 ) {
            ++cnt;
            N/= ind;
        }
        if( cnt )  p[ ++R ]= ind;

        ++ind;
    }
    return R;
}


long long PINEX( int X, int Y ) {
    long long Sol= 0;
    int nr= Desc_factori( Y );
    int k= 1<<nr;
    for( int i= 1;  i<k;  ++i ) {
        int cnt= 0, prod= 1;
        for( int 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() {
    int T;
    in >> T;
    for( int t= 0;  t<T;  ++t ) {
        in >> A >> B;
        out << PINEX( A, B ) << '\n';
    }
    return 0;
}