#include <cstdio>

using namespace std;

int pm[(1000000 >> 6) + 10], prim[1000010], k, q;
long long a, b, v[1000010];

inline void ciur ()
{
    for (int i = 1; ((i * i) << 1) + (i << 1) <= 1000000; ++i)
        if (!(pm[i >> 5] & (1 << (i & 31))))
            for (int j = ((i * i) << 1) + (i << 1); (j << 1) + 1 <= 1000000; j += (i << 1) + 1)
                pm[j >> 5] |= (1 << (j & 31));

    prim[++k] = 2;
    for (int i = 1; 2 * i + 1 <= 1000000; ++i)
        if (!(pm[i >> 5] & (1 << (i & 31)))) prim[++k] = 2 * i + 1;
}

inline void desc ()
{
    int cb = b, x = 0;
    q = 0;
    while (cb > 1)
    {
        if (!(cb % prim[++x])) v[++q] = prim[x];

        while (!(cb % prim[x]))
            cb /= prim[x];
    }
}

inline long long sub ()
{
    int p = 1 << q;
    long long ts = 0LL;

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

        for (int j = 0; j < q; ++j)
            if ((i >> j) & 1) s *= v[j + 1] * 1LL, ++nr;

        if (!(nr % 2)) s = -s * 1LL;
        ts += 1LL * a / s;
    }

    return ts;
}

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

    int n;
    scanf ("%d", &n);

    ciur ();

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

        desc ();
        long long x = 1LL * (1LL * a - 1LL * sub ());

        printf ("%lld\n", x);
    }

    return 0;
}