#include<fstream>

using namespace std;

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

const int nmax = 40;
long long ans, nrp, A, B, p[ nmax ];

void descomp( long long x ) {
    long long i, y;
    nrp = 0;
    y = x;
    for( i = 2; i * i <= x; ++ i ) {
        if ( y % i == 0 ) {
            while ( y % i == 0 ) {
                y /= i;
            }
            p[ ++ nrp ] = i;
        }
    }
    if ( y > 1 ) {
        p[ ++ nrp ] = y;
    }
}
void pinex( int poz, long long acc ) {
    ans += ( A / acc );
    for( int i = poz; i <= nrp; ++ i ) {
        pinex( i + 1, -acc * p[ i ] );
    }
}
void solve() {
    descomp( B );
    ans = 0;
    pinex( 1, 1 );
    fout << ans << "\n";
}
int main() {
    int t;
    fin >> t;
    while ( t -- ) {
        fin >> A >> B;
        solve();
    }
    fin.close();
    fout.close();
    return 0;
}