#include <bits/stdc++.h>

using namespace std;

const int Vmax = 1e6;

bool ciur[Vmax + 1];
long long fact[200];
int nrFactors;
long long primes[80000];
int P;

void gen_ciur()
{
    for ( int i = 2; i <= Vmax; ++i )
        ciur[i] = true;

    for ( int i = 4; i <= Vmax; i += 2 )
        ciur[i] = false;

    primes[++P] = 2;

    for (int i = 3; i <= Vmax; i += 2 )
        if ( ciur[i] )
        {
            primes[++P] = i;

            for (long long j = 1LL * i * i; j <= 1LL * Vmax; j += i)
                ciur[j] = false;
        }
}

void decompose(long long N)
{
    nrFactors = 0;

    for(int i = 1; 1LL * primes[i] * primes[i] <= N && i <= P; ++i)
    {
        if ( N % primes[i] )
            continue;

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

        fact[nrFactors++] = primes[i];
    }

    if (N > 1)
        fact[nrFactors++] = N;
}

long long pinex(long long A)
{
    long long sol = 0;

    for (int i = 1; i < (1 << nrFactors); ++i)
    {
        int nrb = 0;
        long long prod = 1;

        for ( int j = 0; j < nrFactors; ++j )
            if ( i & (1 << j) )
            {
                nrb++;
                prod *= 1LL * fact[j];
            }

        if (nrb & 1)
            sol += A / prod;
        else
            sol -= A / prod;
    }

    return sol;
}

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

    gen_ciur();

    int M;
    long long A, B;

    in >> M;

    while ( M-- )
    {
        in >> A >> B;
        decompose(B);
        out << A - pinex(A) << "\n";
    }

    return 0;
}