#include <iostream>
#include <fstream>
#include <bitset>

using namespace std;

const int Nmax = 1e6 + 1;

bitset <Nmax> ciur;
long long Primes[80000], P;
long long Factors[80000], F;

long long A, B, M, SOL;

void gen()
{
    for ( int i = 2; i < Nmax; ++i )
            ciur[i] = 1;

    for ( int i = 4; i < Nmax; i += 2 )
            ciur[i] = 0;

    Primes[ ++P ] = 2;

    for ( int i = 3; i < Nmax; ++i )
    {
        if ( ciur[i] == 1 )
        {
            Primes[ ++P ] = i;

            for ( int j = 3 * i; j < Nmax; j += 2 * i )
                    ciur[j] = 0;
        }
    }
}

void descomp( long long B )
{
    F = 0;

    for ( int i = 1; i <= P && Primes[i] * Primes[i] <= B; ++i )
    {
        if ( B % Primes[i] ) continue;

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

        Factors[ ++F ] = Primes[i];
    }

    if ( B > 1 )
    {
        Factors[ ++F ] = B;
    }
}

void EIP()
{
    SOL = 0;

    long long lim = ( 1 << F ) - 1;
    long long prod;
    int nr;

    for ( int i = 1; i <= lim; ++i )
    {
        prod = 1, nr = 0;

        for ( int j = 0; j < F; ++j )
                if ( i & ( 1 << j ) )
                {
                    prod *= Factors[F - j];
                    nr++;
                }

        if ( nr % 2 )
                SOL += A / prod;
        else
                SOL -= A / prod;
    }
}

int main()
{
    ifstream f("pinex.in");
    ofstream g("pinex.out");

    gen();

    f >> M;

    while ( M-- )
    {
        f >> A >> B;

        descomp( B );
        EIP();

        g << A - SOL << "\n";
    }

    return 0;
}