#include <cstdio>

using namespace std;

long long n, a, b, k, q;
bool pm[1048576];
int prim[1048576], v[1048576];

void ciur ()
{
    for (int i = 2; i <= 1000; i++)
    {
        if (!pm[i])
            for (int j = i * i; j <= 1000000; j += i)
                pm[j] = true;
    }

    for (int i = 2; i <= 1000000; i++)
        if (!pm[i]) prim[++k] = i;
}

void desc ()
{
    long long B = b, u = 0;
    q = 0;
    while (B > 1)
    {
        u++;

        if (!(B % prim[u])) v[++q] = prim[u];

        while (!(B % prim[u]))
            B /= prim[u];

        if (B > 1 && prim[u] * prim[u] > b)
        {
            v[++q] = B;
            B = 1;
        }
    }
}

long long sub ()
{
    long long ts = 0, p = 1 << q;

    for (int i = 1; i < p; i++)
    {
        long long ci = i, nr = 0, s = 1;

        for(int j = 1; j <= q; j++)
        {
            if (ci % 2) s *= v[j], nr++;
            ci /= 2;
        }

        if (!(nr % 2)) s = -s;

        ts += (long long) a / s;
    }

    return ts;
}

int main ()
{
    freopen ("pinex.in", "r", stdin);
    freopen ("pinex.out", "w", stdout);

    scanf ("%d", &n);

    ciur ();

    for (int i = 1; i <= n; i++)
    {
        scanf ("%lld %lld", &a, &b);

        desc ();
        long long x = (long long) a - sub ();
        printf ("%lld\n", x);
    }

    return 0;
}