#include <fstream>
#include <bitset>
#include <vector>

using namespace std;
const long long nmax = 1e6;
bitset < nmax + 1 > ciur;
vector < long long > primes;
long long p[15];

void precalc ( long long n = nmax ) {
    for ( long long i = 2; i * i <= nmax; i += 1 + i % 2 )
        if ( ciur[i] == 0 )
            for ( long long j = i * i; j <= nmax; j += i )
                ciur[j] = 1;
    for ( long long i = 2; i * i <= nmax; i += 1 + i % 2 )
        if ( ciur[i] == 0 )
            primes.push_back ( i );
}

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

int main() {
    long long q;
    long long a, b;

    fin >> q;
    precalc ();
    while ( q-- ) {
        fin >> a >> b;
        long long d = 0, k = 0;
        while ( d < primes.size () && ( long long ) primes[d] * primes[d] <= b ) {
            if ( b % primes[d] == 0 ) {
                while ( b % primes[d] == 0 )
                    b /= primes[d];
                p[k++] = primes[d];
            }
            d++;
        }
        if ( b > 1 )
            p[k++] = b;

        long long sum = 0;
        for ( long long i = 0; i < ( 1 << k ); i++ ) {
            long long add = ( __builtin_popcount ( i ) % 2 ? -1 : 1 );
            long long prod = 1;
            for ( long long j = 0; j < k; j++ )
                if ( i & ( 1 << j ) )
                    prod *= p[j];
            sum += ( long long ) add * ( a / prod );
        }

        fout << sum << '\n';
    }

    return 0;
}