#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, e; in >> a >> b, s = a; 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 (int i = 1 << Q.size(); e = 1, --i;) {
            for (int j = Q.size(); j--;) if (i & 1 << j) e *= Q[j];
            if (__builtin_popcount(i) & 1) s -= a/e; else s += a/e;}
        out << s << '\n';}
}