#include <fstream>

using namespace std;

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

int v[1000001], n, a, b, q[10001], prim[10001], k, sum;

void ciur(){
    for (int i = 2; i <= 100001; i++) {
        if (!v[i]) {
            prim[++k] = i;
            for (int j = i * 2; j <= 100001; j += i)
                v[j] = 1;
        }
    }
}

int main() {
    in >> n;
    ciur();
    for (int c = 1; c <= n; c++) {
        in >> a >> b;
        int nr = 0, sum = 0;
        for (int i = 1; b > 1; i++) {
            if (b % prim[i] == 0) {
                q[++nr] = prim[i];
                while (b % prim[i] == 0)
                    b /= prim[i];
            }
            if (prim[i] * prim[i] > b && b > 1) {
                q[++nr] = b;
                b = 1;
            }
        }
        for (int i = 1; i < (1 << nr); i++) {
            int prod = 1, semn = 0;
            for (int j = 0; j < nr; j++) 
                if (i & (1 << j)) {
                    prod *= q[j + 1];
                    semn++;
                }
                sum += (a / prod * (semn % 2 == 1 ? 1 : -1));
        }
        out << a - sum << '\n';
    }
    return 0;
}