#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;
int ciur[1000005];
int64_t sol;
 
void init() {
    in >> M;
 
    int64_t i;
    for (i = 2; i * i < 1000000; ++i)
        if (!ciur[i]) {
            p.push_back(i);
 
            for (int64_t j { i * i }; j < 1000000; j += i)
                ciur[j] = false;
        }
 
    for (; i < 1000000; ++i)
        if (!ciur[i])
            p.push_back(i);
}
 
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';
    }
}