#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] = true;
        }
}

void findSets(int k, int64_t prod, int noSets) {
    if (k == d.size()) {
        if (prod != 1)
            sol += (noSets % 2 ? 1 : -1) * (A / prod);
        return;
    }

    findSets(k + 1, prod, noSets);
    findSets(k + 1, prod * d[k], noSets + 1);
}
 
inline 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;
    findSets(0, 1, 0);
}
 
int main() {
    init();
 
    while (M--) {
        in >> A >> B;
        solve();
        out << A - sol << '\n';
    }
}