#include <fstream>

using namespace std;

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

int n;
bool prim[(1<<19)];
long long a, b, sol;
int pr[(1<<17)], np, i;
long long fct[(1<<16)], exp[(1<<16)], nf;

void ciur(int n) {
    int i, j;
    pr[(np=1)] = 2;
    for (i = 1; (i<<1) < n; i++)
        if (prim[i] == 0) {
            pr[++np] = (i<<1)+1;
            for (j = (i<<1)+i+1; (j<<1) < n; j+= (i<<1)+1)
                prim[j] = 1;
        }
}

void factorizare() {
    int i = 1;
    nf = 0;
    while (b > 1) {
        if ((pr[i]*pr[i] > b && b > 1) || i > np) {
            fct[++nf] = b;
            exp[nf] = 1;
            b = 1;
        }
        else if (b%pr[i] == 0) {
            fct[++nf] = pr[i];
            while (b%pr[i] == 0)
                exp[nf]++, b /= pr[i];
        }
        i++;
    }
}

void pinex() {
    long long fac;
    int i, j, cnt;

    sol = a;
    for (i = 1; i < (1 << nf); i++) {
        fac = 1, cnt = 0;
        for (j = 0; j < nf; j++)
            if ((i&(1<<j)) != 0)
                fac *= fct[j+1], cnt++;
        if (cnt%2)
            sol -= a/fac;
        else sol += a/fac;
    }
}

int main() {
    ciur(1e6);

    f >> n;
    while (n--) {
        f >> a >> b;
        factorizare();
        pinex();
        g << sol << '\n';
    }
    return 0;
}