#include <fstream>
#define mF "pinex"
std::ifstream in(mF ".in");
std::ofstream out(mF ".out");
constexpr int N = 1000001;
#include <bitset>
#include <vector>
using LL = long long;
int main()
{
    std::bitset<N> C; std::vector<int> P; for (int i = 2, j; i < N; i++) if (!C[i]) for (j = i<<1, P.push_back(i); j < N; j += i) C[j] = true;
    int m; in >> m; while (m--) {
        LL a, b, s = 0; in >> a >> b; std::vector<int> Q;
        for (int p: P) if (b/p < p) break; else if (!(b % p)) for (Q.push_back(p); !(b % p);) b /= p;
        if (b != 1) Q.push_back(b); for (LL i = 1LL << Q.size(), e, c; e = 1, c = 0, --i;) {
            for (LL j = Q.size(); j--;) if (i & 1LL << j) e *= Q[j], c++;
            if (c) if (c & 1) s += a/e; else s -= a/e;}
        out << a - s << '\n';}
}