#include <bits/stdc++.h>

using LL = long long;

const int PRIME_MAX = (int)10e6;

LL a, b;

std::vector<int> primes;
std::vector<LL> factors;
std::bitset<PRIME_MAX> not_prime;

void sieve() {
    not_prime[1] = 1;

    primes.push_back(2);

    for (int i = 4; i < PRIME_MAX; i += 2)
        not_prime[i] = 1;

    for (int i = 3; i < PRIME_MAX; i += 2) {
        if (not_prime[i])
            continue;

        primes.push_back(i);

        for (int j = 2 * i; j < PRIME_MAX; j += i)
            not_prime[j] = 1;
    }
}

void find_factors() {
    factors.clear();

    for (auto p: primes) {
        if (p * p > b)
            break;

        if (b % p == 0) {
            factors.push_back(p);

            while (b % p == 0)
                b /= p;
        }
    }

    if (b > 1)
        factors.push_back(b);
}

LL pinex() {
    LL result  = a;

    for (int subset = 1; subset < (1 << factors.size()); subset++) {
        LL product = 1;
        int sign = 1;

        for (int j = 0; j < factors.size(); j++) {
            if (subset & (1 << j)) {
                product *= factors[j];
                sign *= -1;
            }
        }

        result += sign * a / product;
    }

    return result;
}

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

    sieve();

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

    while (t--) {
        scanf("%lld %lld", &a, &b);
        find_factors();
        printf("%lld\n", pinex());
    }
}