#include <fstream>
#include <cmath>

using namespace std;

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

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

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

    }
}

void calc() {
    int i, j;
    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];
        nr = (nr%2?-1:1);
        sol += 1LL*nr*x/oa;
    }
}

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