/**
Răspundeţi la M întrebări de tipul: „dându-se două numere naturale A şi B,
să se determine numărul de numere naturale mai mici sau egale cu A şi prime
cu B”. Două numere naturale x, y sunt prime între ele dacă cmmdc(x, y) = 1.
*/

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

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

const int MAXP = 1000005;
using LL = long long;
bool ciur[MAXP];
vector<LL> p;
LL T, A, B;
vector<LL> d;
LL prod;
LL s[20];
LL rez;

void Ciur();
void Solve();
void Back( LL h, vector<LL>::iterator it );

int main()
{
    LL i;

    Ciur();

   /* for ( const auto& x : p )
        fout << x << ' ';   */

    fin >> T;

    for ( i = 1; i <= T; i++ )
    {
        fin >> A >> B;

        Solve();

        rez = 0;
    }

    fin.close();
    fout.close();
    return 0;
}

void Ciur()
{
    LL i, j;

    for ( i = 2; i * i < MAXP; i++ )
        if ( !ciur[i] )
        {
            p.push_back(i);
            for ( j = i * 2; j < MAXP; j += i )
                ciur[j] = 1;
        }
    for ( ; i < MAXP; i++ )
        if ( !ciur[i] )
            p.push_back(i);
}

void Solve()
{
    LL i, j;

    d.clear();
    for ( const auto& x : p )
        if ( B % x == 0 )
        {
            d.push_back(x);
            while ( B % x == 0 ) B /= x;
        }
    if ( B > 1 )
        d.push_back(B);

    Back(1, d.begin());

    fout << A - rez << '\n';
}

void Back( LL h, vector<LL>::iterator it )
{
    prod = 1;
    for ( LL i = 1; i < h; i++ )
        prod *= s[i];

    if ( prod != 1 )
    {
        if ( ( h - 1 ) % 2 == 1 )
            rez += ( A / prod );
        else
            rez -= ( A / prod );
    }

    while ( it != d.end() )
    {
        s[h] = *it;
        Back(h + 1, ++it);
    }
}