#include <fstream>
#include <vector>
#include <cmath>
using namespace std;

ifstream is("pinex.in");
ofstream os("pinex.out");

#define sqrtB 1000000
#define ll long long

ll N, A, B;

vector <int> Prime; // vector de numere prime
vector <int> Fact; // factorii primi a lui B
bool notPrime[sqrtB+5]; // daca notPrime[x] este fals atunci x este prim

void Sieve();
void solveQuery();

int main()
{
    is >> N;
    Sieve();

    for ( int i = 1; i <= N; ++i )
    {
        is >> A >> B;
        solveQuery();
        Fact.clear();
    }

    is.close();
    os.close();
}

void Sieve()
{
    for ( int i = 2; i <= sqrtB; ++i )
    {
        if ( !notPrime[i] )
        {
            Prime.push_back(i);
            for ( int j = 2 * i; j <= sqrtB; j += i )
                notPrime[j] = true;
        }
    }
}

void solveQuery()
{
    int it(0); // indexul curent al vectorului Prime
    while ( B != 1 )
    {
        if ( B % Prime[it] == 0 )
        {
            Fact.push_back(Prime[it]);
            while ( B % Prime[it] == 0 )
                B /= Prime[it];
        }
        ++it;
        if ( Prime[it] > sqrt(B) && B > 1 ) // nu are rost sa cautam numere prime mai mari ca sqrtB
        {
            Fact.push_back(B);
            break;
        }
    }
    int nrF = Fact.size();
    ll prod;
    ll Sol(0);
    int nr(0);
    for ( int i = 1; i < (1<<nrF) ; ++i ) // generam submultimile factorilor primi ai lui B
    {
        prod = 1;
        nr = 0;
        for ( int j = 0; j < nrF; ++j ) // parcurgem fiecare bit si inmultim factorii corespunzatori bitilor de 1
        {
            if ( (1 << j) & i )
            {
                nr++;
                prod *= Fact[j];
            }
        }
        if ( nr & 1)
            Sol += (A/prod);
        else
            Sol -= (A/prod);
    }
    os << A - Sol << '\n';
}