#include <fstream>
#include <iostream>

using namespace std;

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

bool prim[1000003];
int fp[1000000], nf, fc[1000000], t;
long long a, b, sol, pro;
int i, j, n, m, nr;

void ciur() {
    for (fp[nf=1]=2, i = 3; i <= 1000001; i+=2)
        if (prim[i] == 0)
            for (fp[++nf] = i, j = i+i; j <= 1000001; j += i)
                prim[j] = 1;
}

long long query() {
    t = 0;
    int i, j;
    for (i = 1; b > 1; i++) {
        if (b%fp[i]==0){
            while (b%fp[i] == 0) b /= fp[i];
            fc[++t] = fp[i];
        }

        if (1LL*fp[i]*fp[i] > b && b > 1) {
            fc[++t] = b;
            b = 1;
        }
    }
    sol = a;
    for (i = 1; i < (1<<t); i++) {
        pro = 1, nr = 0;
        for (j = 0; j < t; j++)
            if ((i&(1<<j)))
                pro = pro*fc[j+1], nr++;

        if (nr%2)
            sol -= 1LL*a/pro;
        else sol += 1LL*a/pro;
    }


    return sol;
}

int main() {
    ciur();
    f >> n;
    for (j = 1; j <= n; j++) {
        f >> a >> b;
        g << query() << '\n';
    }
}