#include <cstdio>
#include <vector>
#include <cstdint>
#include <climits>

#define NMAX 1000000

static size_t sol[NMAX];
static unsigned char sieve[NMAX / CHAR_BIT];
static std::vector<int64_t> b_divs;
static int64_t a;

static void recurse(size_t lvl, size_t n, int64_t *acc)
{
    size_t i;
    int64_t result = 1;

    if (lvl == n) {
        for (i = 0; i < n; i++) {
            result *= b_divs[sol[i]];
        }

        if (n & 1) {
            *acc += a / result;
        } else {
            *acc -= a / result;
        }

    } else {
        for (i = lvl == 0 ? 0 : sol[lvl - 1] + 1; i < b_divs.size(); i++) {
            sol[lvl] = i;
            recurse(lvl + 1, n, acc);
        }
    }
}

int main(void)
{
    int m;
    size_t i, j;
    int64_t b, acc;
    std::vector<int64_t> primes;

    for (i = 2; i <= NMAX; i++) {
        if ((sieve[i / CHAR_BIT] & (1 << (i & (CHAR_BIT - 1)))) == 0) {
            primes.push_back(i);

            for (j = 2; i * j <= NMAX; j++) {
                sieve[(i * j) / CHAR_BIT] |= 1 << ((i * j) & (CHAR_BIT - 1));
            }
        }
    }

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

    scanf("%d", &m);

    while (m--) {
        scanf("%lld %lld", &a, &b);
        b_divs.clear();

        for (i = 0; i < primes.size() && primes[i] <= a; i++) {
            if (b % primes[i] == 0) {
                b_divs.push_back(primes[i]);
            }
        }

        if (b_divs.size() == 0) {
            b_divs.push_back(b);
        }

        acc = 0;

        for (i = 1; i <= b_divs.size(); i++) {
            recurse(0, i, &acc);
        }

        printf("%lld\n", a - acc);
    }

    return 0;
}