#include <fstream>
#include <vector>

std::vector<long long> factors(long long x) {
    std::vector<long long> ans;

    long long d = 2;

    while (x > 1) {
        int p = 0;
        while (x % d == 0) x /= d, p++;
        if (p) ans.push_back(d);
        d++;

        if (x > 1 && d * d > x) d = x;
    }
    return ans;
}

int main() {
    std::ifstream input("pinex.in");
    std::ofstream output("pinex.out");

    int t;
    input >> t;
    while (t--) {
        long long a, b;
        input >> a >> b;

        auto fact = factors(b);
        int size = (int) fact.size();
        long long ans = 0;
        for (int mask = 1; mask < (1 << size); ++mask) {
            int cnt = __builtin_popcount(mask);

            long long res = 1;

            for (int i = 0; i < size; ++i) {
                if (mask & (1 << i)) res *= fact[i];
            }
            res = a / res;

            if (cnt & 1) ans += res;
            else ans -= res;
        }
        output << a - ans << '\n';
    }
    return 0;
}