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

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

void precalc ( int n = nmax ) {
    for ( int i = 2; i * i <= nmax; i += 1 + i % 2 )
        if ( ciur[i] == 0 )
            for ( int j = i * i; j <= nmax; j += i )
                ciur[j] = 1;
    for ( int 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() {
    int q;
    long long a, b;

    fin >> q;
    precalc ();
    while ( q-- ) {
        fin >> a >> b;
        int 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 ( int i = 0; i < ( 1 << k ); i++ ) {
            int add = ( __builtin_popcount ( i ) % 2 ? -1 : 1 );
            long long prod = 1;
            for ( int j = 0; j < k; j++ )
                if ( i & ( 1 << j ) )
                    prod *= p[j];
            sum += add * ( a / prod );
        }

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

    return 0;
}