#include <cstdio>
using namespace std;
const int NMAX = 1000000;
bool c[NMAX + 5];
int p[NMAX + 5], a, v[25], l;
long long solve(int c)
{
    long long nr = -1;
    for (int i = 0; i <= l; ++i)
        if ((c & (1 << i)) != 0)
            nr = nr * -v[i];
    return a/nr;
}
void ciur()
{
    for (int i = 4; i <= NMAX; i += 2)
        c[i] = 1;
    for (int i = 3; i <= 1000; i += 2)
        if (c[i] == 0)
            for (int j = i * i; j <= NMAX; j += 2 * i)
                c[j] = 1;

    p[0] = 0;
    for (int i = 2; i <= NMAX; ++i)
        if (c[i] == 0)
            p[++p[0]] = i;
}
int main()
{
    freopen("pinex.in", "r", stdin);
    freopen("pinex.out", "w", stdout);

    int t, lim;
    long long ans, b;
    ciur();
    for (scanf("%d", &t); t > 0; --t)
    {
        scanf("%lld %lld", &a, &b);
        l = -1;
        for (int i = 1; p[i] * p[i] <= b && i <= p[0] ; ++i)
            if (b % p[i] == 0)
            {
                v[++l] = p[i];
                while (b % p[i] == 0)
                    b /= p[i];
            }
        if (b > 1)
            v[++l] = b;

        lim = (1 << (l + 1)); ans = 0;
        for (int i = 1; i < lim; ++i)
            ans += solve(i);
        printf("%lld\n", a - ans);
    }

    return 0;
}