#include <fstream>
#include <vector>
using namespace std;
 
ifstream in { "pinex.in" };
ofstream out { "pinex.out" };

const int VAL_MAX { 1000000 };
 
int M;
int64_t A, B;
vector<int64_t> p;
int ciur[VAL_MAX + 5];
int64_t sol;
 
void init() {
    in >> M;
 
    for (int64_t i = 2; i * i <= VAL_MAX; ++i)
        if (!ciur[i]) 
            for (int64_t j { i * i }; j <= VAL_MAX; j += i)
                ciur[j] = false;
 
    for (int i { 2 }; i <= VAL_MAX; ++i)
        if (!ciur[i])
            p.push_back(i);
}
 
void solve() {
    vector<int> d;
    for (int i { 0 }; i < int(p.size()) && 1LL * p[i] * p[i] <= B; ++i)
        if (B % p[i] == 0) {
            d.push_back(p[i]);
            while (B % p[i] == 0)
                B /= p[i];
        }
 
    if (B != 1)
        d.push_back(B);
 
    sol = 0;
    for (int config { 0 }; config < 1 << d.size(); ++config) {
        int64_t prod { 1 }, sgn { 1 };
        for (int prime { 0 }; prime < d.size(); ++prime)
            if (config & (1 << prime)) {
                sgn *= -1;
                prod *= d[prime];
            }
 
        sol += sgn * (A / prod);
    }
}
 
int main() {
    init();
 
    while (M--) {
        in >> A >> B;
        solve();
        out << sol << '\n';
    }
}