#include <fstream>

using namespace std;

const int DIM1 = 1000010;
const int DIM2 = 100010;

long long m, a, b, primCnt, k, p, sol;
int prim[DIM1], v[DIM2], x[13];
bool f[DIM1];

void backtrack(int step) {
    for (int i = x[step - 1] + 1; i <= k; i++) {
        x[step] = i;
        p = p * v[i];
        if (step % 2 == 0)
            sol -= a / p;
        else
            sol += a / p;

        if (step < k)
            backtrack(step + 1);

        p = p / v[i];
    }
}

int main() {
    ifstream fin("pinex.in");
    ofstream fout("pinex.out");

    for (int i = 2; i < DIM1; i++) {
        if (!f[i]) {
            for (int j = i + i; j < DIM1; j += i)
                f[j] = true;
            prim[++primCnt] = i;
        }
    }

    fin >> m;
    for (int i = 1; i <= m; i++) {
        fin >> a >> b;

        long long aux = b;
        k = 0;
        for (int j = 1; j <= primCnt && 1LL * prim[j] * prim[j] <= aux; j++) {
            if (aux % prim[j] == 0) {
                v[++k] = prim[j];
                while (aux % prim[j] == 0)
                    aux /= prim[j];
            }
        }
        if (aux != 1)
            v[++k] = aux;

        p = 1;
        sol = 0;
        x[0] = 0;
        backtrack(1);

        fout << a - sol << '\n';
    }

    return 0;
}