#include <fstream>

using namespace std;

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

long long comp[100005],q,t,x,k;
long long zac[1000005], np;
bool prim[1000005];

long long query() {
    long long t = 0, cnt = 0, i,j, x1 = x;
    long long tmp = 0, t2 = 0, sol = 0;

    for (i = 1; k > 1; i++) {
        if (k%zac[i]==0) {
            cnt = 0;
            while (k%zac[i]==0)
                k /= zac[i];
            comp[++t] = zac[i];
            if (1LL*zac[i]*zac[i] >k && k > 1) {
                comp[++t] = k;
                break;
            }
        }
    }

    for (i = 1; i < (1<<t);i++) {
        t2 = 1,cnt = 0;
        for (j = 0; j <= t;j++)
            if ((i&(1<<j))) {
                //g<<comp[j+1]<< ' ';
                t2 = 1LL*t2*comp[j+1];
                cnt++;
            }
            //g<<'\n';
        if (cnt %2)
            cnt = 1;
        else cnt = -1;

        tmp+= 1LL*cnt*x/t2;
    }

    sol = x-tmp;
    return sol;
}

void ciur() {
    int i, j;
    prim[2] = 0;
    zac[np=1] = 2;
    for (i = 3; i <= 1000000; i+=2)
        if (prim[i] == 0) {
            zac[++np] = i;
            //g<<i << ' ';
            for (j=3*i; j <= 1000000; j += 2*i)
                prim[j] = 1;
        }
    //g << '\n';
}

int main() {
    ciur();
    f >> q;
    while (q--) {
        f >>x>>k;
        g << query() << '\n';
    }
    return 0;
}