# include <fstream>

using namespace std;

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

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

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

    return 1;
}

void backtracking (int e)
{
    if (e == w + 1)
    {
        for (int 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 (int i = 1; i <= nr; i++)
    {
        q[e] = divizor[i];

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

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

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

    in >> t;

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

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

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

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

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

            backtracking(1);
        }

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

        s = 0;

        nr = 0;

    }

    return 0;
}