#include <cstdio>
#include <cmath>

using namespace std;

bool prim[1000005];
int p[80005], np;
long long oa, sol;
int fact[80005], t, nr,i,j;
long long x, k;
int n;

void ciur() {
    p[++np] = 2;
    for (i = 3; i <= 1000000; i=i+2) {
        if (prim[i] == 0) {
            p[++np] = i;
            for (j = i+i+i; j <= 1000000; j =j+ (i<<1))
                prim[j] = 1;
        }
    }
}

void calc() {
    t = 0;
    for (i = 1; k > 1; i++) {
        if (k%p[i]==0) {
            fact[++t] = p[i];
            while (k%p[i]==0)
                k/=p[i];
        }
        if (p[i]>sqrt(k) && k > 1) {
            fact[++t] = k;
            k = 1;
        }
    }

    sol = x;
    for (i = 1; i < (1<<t); i++) {
        oa = 1, nr = 0;
        for (j = 0; j < t; j++)
            if (((1<<j)&i))
                nr++, oa = 1LL*oa*fact[j+1];
        if (nr&1) nr = -1;
            else  nr = 1;
        sol += 1LL*nr*x/oa;
    }
}

int main() {
    ciur();
    freopen("pinex.in","r",stdin);
    freopen("pinex.out","w",stdout);

    scanf("%d\n",&n);
    while (n--) {
        scanf("%lld %lld\n",&x,&k);
        calc();
        printf("%lld\n",sol);
    }
    return 0;
}