#include <fstream>
#include <vector>
#include <bitset>
#include <cmath>

using namespace std;

ifstream f("pinex.in");
ofstream g("pinex.out");

#define PMAX 1000005

int m, a, b;
vector<int> prime;

void Eratostene() {
    bitset<PMAX> ciur;
    for (int i = 2; i < PMAX; ++i)
        if (!ciur[i]) {
            for (int j = 2 * i; j < PMAX; j += i)
                ciur.set(j);
            prime.push_back(i);
        }
}

void solve() {
    vector<int> factori;
    int ind = -1;
    while (b > 1) {
        ind++;
        if (b % prime[ind] == 0) {
            factori.push_back(prime[ind]);
            while (b % prime[ind] == 0)
                b /= prime[ind];
        }
        if (prime[ind] > sqrt(b) && b > 1) {
            factori.push_back(b);
            b = 1;
        }
    }

    int nrf = (int) factori.size();
    int putf = 1 << nrf;
    long long sol = a;
    for (int i = 1; i < putf; ++i) {
        int nrm = 0;
        long long prod = 1;
        for (int j = 0; j < nrf; ++j)
            if (i & (1 << j)) {
                nrm++;
                prod = prod * factori[j];
            }
        if (nrm % 2)
            nrm = -1;
        else
            nrm = 1;
        sol = sol + 1LL * nrm * a / prod;
    }
    g << sol << '\n';
}

int main() {
    Eratostene();
    f >> m;
    for (int i = 0; i < m; ++i) {
        f >> a >> b;
        solve();
    }
    return 0;
}