# include <fstream>

using namespace std;

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

unsigned long long n, w;
unsigned long long q[1000000];
unsigned long long t, a, b, k, s, nr, prod = 1;
unsigned long long p[1000000], OK[1000000], divizor[1000000];

int verifica (unsigned long long t)
{
    for (unsigned long long i = 1; i <= t - 1; i++)
        if (q[i] == q[t] || q[i] > q[i+1])
            return 0;

    return 1;
}

void backtracking (unsigned long long e)
{
    if (e == w + 1)
    {
        for (unsigned long long i = 1; i <= w; i++)
            prod = prod * q[i];

        if (w % 2 == 1)
            s = s + a / prod;

        else

            s = s - a / prod;

            prod = 1;

        return;
    }

    for (unsigned long long i = 1; i <= nr; i++)
    {
        q[e] = divizor[i];

        if (verifica(e)) backtracking(e + 1);
    }
}

int main()
{
    for (unsigned long long i = 2; i <= 1000000; i++)
    {
        if (OK[i] == 0)
        {
            for (unsigned long long j = i * i; j <= 1000000; j = j + i)
                OK[j] = 1;

            k++;
            p[k] = i;
        }
    }

    in >> t;

    for (unsigned long long i = 1; i <= t; i++)
    {
        in >> a >> b;

        for (unsigned long long j = 1; j <= k; j++)
        {
            if (p[j] > b)
                break;

            if (b % p[j] == 0)
            {
                nr++;

                divizor[nr] = p[j];
            }
        }

        for (unsigned long long x = 1; x <= nr; x++)
        {
            w = x;

            backtracking(1);

            for (unsigned long long l = 1; l <= nr; l++)
                q[l] = 0;

            prod = 1;
        }

        out << a - s << '\n';

        s = 0;

        nr = 0;

    }

    return 0;
}