#include <iostream>
#include <fstream>
#include <algorithm>
#include <cmath>

using namespace std;

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

const int NMAX = 30 + 5;
const int FMAX = 8e5 + 5;
const int PMAX = 1e6 + 5;

long long m, a, b;
long long fact[NMAX];
int fprim[FMAX];
bool prim[PMAX];

void precalc()
{
    fill(prim + 2, prim + PMAX, 1);

    for (int i = 2; i < PMAX; ++i)
        if (prim[i])
        {
            for (int j = 2 * i; j < PMAX; j += i)
                prim[j] = false;
            fprim[++fprim[0]] = i;
        }
}

int main()
{
    precalc();

    fin >> m;
    while (m--)
    {
        fin >> a >> b;

        long long t = 0, d = 0;
        while (b > 1)
        {
            ++d;
            if (b % d == 0)
            {
                fact[++t] = fprim[d];
                while (b % fprim[d] == 0)
                    b /= fprim[d];
            }

            if (fprim[d] > sqrt(b) && b > 1)
            {
                fact[++t] = b;
                b = 1;
            }
        }

        long long sol = a;
        for (int i = 1; i < (1 << t); ++i)
        {
            long long nr = 0, prod = 1;
            for (int j = 0; j < t; ++j)
                if ((1 << j) & i)
                {
                    prod = 1LL * prod * fact[j + 1];
                    ++nr;
                }
            if (nr % 2) nr = -1;
            else nr = 1;

            sol += 1LL * nr * a / prod;
        }

        fout << sol << '\n';
    }

    return 0;
}