#include <bits/stdc++.h>
using namespace std;

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

int prime(int B, int prim[]) {
    int k = 0;
    for (int d = 2; d <= B; d++) {
        if (B % d == 0) {
            prim[k++] = d;
            while (B % d == 0) B /= d;
        }
    }
    if (k == 0) prim[0] = B;
    return k;
}

int main(void) {
    int n, A, B;
    f >> n;
    for (int i = 0; i < n; i++) {
        f >> A >> B;

        int prim[1001], len = prime(B, prim);
        int pos = 0, numit = 1;
        for (int i = 0; i < len; i++) {
            pos += (A / prim[i]);
            numit *= prim[i];
            for (int j = i + 1; j < len; j++) {
                pos -= (A / (prim[i] * prim[j]));
            }
        }
        pos += (A / numit);

        g << A - pos << '\n';
    }
}