#include <fstream>
#include <vector>
using namespace std;

ifstream in { "pinex.in" };
ofstream out { "pinex.out" };

int M;
int64_t A, B;
vector<int64_t> p;
vector<int64_t> d;
int64_t sol;

void init() {
    in >> M;

    const int B_MAX { 1000005 };
    vector<bool> ciur(B_MAX);
    for (int64_t i { 2 }; i <= B_MAX; ++i)
        if (!ciur[i]) {
            p.push_back(i);

            for (int64_t j { i * i }; j <= B_MAX; j += i)
                ciur[j] = false;
        }
}

void solve() {
    d.clear();
    for (const auto& b : p) {
        if (b * b > B)
            break;

        if (B % b == 0) {
            d.push_back(b);
            while (B % b == 0)
                B /= b;
        }
    }

    if (B != 1)
        d.push_back(B);

    sol = 0;
    for (int config { 1 }; config < 1LL << d.size(); ++config) {
        int noSets { 0 };
        int64_t prod { 1 };
        for (int prime { 0 }; prime < int(d.size()); ++prime)
            if (config & (1 << prime)) {
                ++noSets;
                prod *= d[prime];
            }

        sol += (noSets % 2 ? 1 : -1) * (A / prod);
    }
}

int main() {
    init();

    while (M--) {
        in >> A >> B;
        solve();
        out << A - sol << '\n';
    }
}