#include<fstream>
#include<bitset>

using namespace std;

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

const int nmax = 40;
const int nrmax = 1000000;
const int pmax = 80000;
long long ans, nrp, w, A, B;
long long p[ nmax ], prim[ pmax ];
bitset <nrmax> ciur;

void calc_prime() {
    for( int i = 2; i * i < nrmax; ++ i ) {
        if ( ciur[ i ] == 0 ) {
            for( int j = i * i; j < nrmax; j += i ) {
                ciur[ j ] = 1;
            }
        }
    }
    w = 0;
    for( int i = 2; i < nrmax; ++ i ) {
        if ( ciur[ i ] == 0 ) {
            prim[ w ++ ] = i;
        }
    }
}
void descomp( long long x ) {
    long long y;
    nrp = 0;
    y = x;
    for( int i = 0; prim[ i ] * prim[ i ] <= x; ++ i ) {
        if ( y % prim[ i ] == 0 ) {
            while ( y % prim[ i ] == 0 ) {
                y /= prim[ i ];
            }
            p[ ++ nrp ] = prim[ 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 ] );
    }
}
inline void solve() {
    descomp( B );
    ans = 0;
    pinex( 1, 1 );
    fout << ans << "\n";
}
int main() {
    int t;
    fin >> t;
    calc_prime();
    while ( t -- ) {
        fin >> A >> B;
        solve();
    }
    fin.close();
    fout.close();
    return 0;
}