#include <fstream>
#include <cmath>
#define LL long long

using namespace std;

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

const int nmax = 1000005;
int p[78000], np, n, i;
int fct[30];
bool prim[nmax];
LL a, b;

void ciur(int n) {
    int i, j, sqn = sqrt(n);

    p[np=1] = 2;
    for (i = 3; i <= sqn; i += 2)
        if (prim[i] == 0) {
            p[++np] = i;
            for (j = i*i; j <= n; j += 2*i)
                prim[j] = 1;
        }
}

void factorizare(LL b, int *fct, int &n) {
    int i = 1;
    n = 0;
    while (b > 1 && i <= np) {
        if (p[i]*p[i] > b) {
            fct[n++] = b;
            b = 1;
        } else if (b%p[i] == 0) {
            fct[n++] = p[i];
            while (b%p[i] == 0) b /= p[i];
        }

        i++;
    }
}

LL pinex() {
    int t, i, j, cnt;
    LL prod, sol = a;

    factorizare(b, fct, t);

    for (i = 1; i < (1<<t); i++) {
        cnt = 0, prod = 1;
        for (j = 0; j < t; j++)
            if ((i&(1<<j)) != 0)
                cnt++, prod *= fct[j];

        if (cnt%2)
            sol -= a/prod;
        else sol += a/prod;
    }
    return sol;
}

int main() {
    ciur(1e6);
    f >> n;
    while (n--) {
        f >> a >> b;
        g << pinex() << '\n';
    }

    return 0;
}