#include <bits/stdc++.h>

using namespace std;

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

const int PMAX = 1000000;

int N;
vector <long long> primes;
vector <long long> factors;

void  get_primes() {
    bitset<PMAX + 2> bset;

    bset[2] = 1;
    for( int i = 3; i <= PMAX; i += 2 )
        bset[i] = 1;

    for( int i = 3; i <= PMAX; i += 2 )
        if( bset[i] )
            for( int j = 3; i * j <= PMAX; j += 2 )
                bset[i * j] = 0;

    primes.push_back( 2 );
    for( int i = 3; i <= PMAX; ++i )
        if( bset[i] )
            primes.push_back( i );
}

long long solve( long long A, long long B ) {
    long long _ans = 0;

    factors.clear();

    for( int i = 0; i < primes.size() && 1LL * primes[i] * primes[i] <= B; ++i )
        if( B % primes[i] == 0 ) {
                factors.push_back( primes[i] );

                while( B % primes[i] == 0 )
                    B /= primes[i];
        }

    if( B > 1 )
        factors.push_back( B );

    int fsz = factors.size();

    /// GENERAM TOATE SUBMULTIMILE POSIBILE  ( ALE CELOR "fsz" FACTORI PRIMI AI LUI B )
    /// FOLOSIND OPERATII PE BITI

   // for( int i = 0; i < factors.size(); ++i )
    //    fout << factors[i] << ' ';
    //fout << '\n';

    for( long long i = 1; i < ( 1LL << fsz ); ++i ) {
        int cnt = 0;
        long long prod = 1; /// PRODUSUL FACTORILOR

        //fout << "*\n";

        for( int j = 0; j < fsz; ++j )
            if( ( 1LL << j ) & i ) {
                ++cnt;
                prod *= factors[j];
            }
        //fout << i << ' ' << cnt << ' ' << prod << '\n';


        if( cnt % 2 ) _ans += 1LL * A / prod;
        else _ans -= 1LL * A / prod;
    }

    //fout << _ans << '\n';

    return A - _ans;
}

int main()
{
    get_primes();

    fin >> N;

    long long A, B;
    for( int i = 1; i <= N; ++i ) {
        fin >> A >> B;

        fout << solve( A, B ) << '\n';
    }

    return 0;
}