#include <fstream>
#include <vector>

#define in "pinex.in"
#define out "pinex.out"
#define LL long long
#define Max_Size 1000000

std :: ifstream f(in);
std :: ofstream g(out);

int M;
LL A, B;
bool Viz[Max_Size + 3];

std :: vector < LL > Ciur;
std :: vector < int > D;

inline void Eratostene()
{
    for(int i = 2; i <= Max_Size; i += 2)   Viz[i] = 1;

    Ciur.push_back(2);

    for(int i = 3; i <= Max_Size; i += 2)
        if(!Viz[i])
        {
            Ciur.push_back(i);
            for(int j = i; j <= Max_Size; j += i)   Viz[j] = 1;
        }
}

inline void Back(LL &rez)
{
    for(int i = 1; i < (1 << D.size()); ++i)
    {
        int nr = 0;
        LL prod = 1;

        for(int j = 0; j < D.size(); ++j)
            if(i & (1 << j))
            {
                prod *= D[j];
                ++nr;
            }

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

inline void Solve()
{
    int i = 0;

    while(i < Ciur.size() && B > 1)
    {
        if(!(B % Ciur[i]))
        {
            D.push_back(Ciur[i]);
            while( !(B % Ciur[i]))  B /= Ciur[i];
        }

        ++i;
    }

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

    LL rez = A;
    Back(rez);

    g << rez << '\n';

    D.clear();
}

int main()
{
    Eratostene();

    f >> M;

    for(int i = 1; i <= M; ++i)
    {
        f >> A >> B;
        Solve();
    }

    g.close();
    return 0;
}