#include <fstream>

using namespace std;

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

const int VMAX = 1000000,
          PMAX = 78500;

bool v[VMAX + 1];
long long P[PMAX], nrP, n, fact[31];

void ciur(int n) {
    int i, j;
    v[0] = v[1] = 1;

    for (i = 4; i <= n; i += 2)
        v[i] = 1;

    for (int i = 3; i * i <= n; i += 2)
        if (v[i] == 0)
            for (int j = i * i; j <= n; j += i)
                v[j] = 1;

    nrP = 1;
    P[1] = 2;
    for (int i = 3; i <= n; i += 2)
        if (v[i] == 0)
            P[++nrP] = i;
}

long long nr(long long a, long long b) {
    long long d = 0, p = 0;
    while (b > 1) {
        d++;
        if (b % P[d] == 0) {
            fact[++p] = P[d];
            while (b % P[d] == 0)
                b /= P[d];
        }
        if (P[d] * P[d] > b && b > 1)
            fact[++p] = b, b = 1;
    }

    long long sol = a;
    for (int i = 1; i < (1 << p); i++) {
        long long nr = 0, prod = 1;
        for(int j = 0; j < p; j++)
            if ((1 << j) & i) {
                prod = 1LL * prod * fact[j + 1];
                nr++;
            }

        if (nr % 2) nr = -1;
        else nr = 1;

        sol = sol + 1LL * nr * a / prod;
    }
    return sol;
}

int main() {
    
    in >> n;

    ciur(1000000);

    while (n--) {
        int A, B;
        in >> A >> B;
        out << nr(A, B) << '\n';
    }

    return 0;
}