#include <fstream>
#include <vector>
#include <math.h>

using namespace std;

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

vector<bool> prim(1000000);
vector<int> prims;
vector<int> divs (1000000);

long long A, card_u;
int n;

void rec(int pos, int left, long long res) {
    if (pos == n) {
        if (!left) card_u += A / res;
        return;
    }
    if (!left) {
        card_u += A / res;
        return;
    }

    rec(pos+1, left, res);
    rec(pos+1, left-1, res * divs[pos]);
}

int main() {
    for (int i = 2; i < 1000000; i++)
        if (!prim[i]) {
            prims.push_back(i);
            for (int j = 2 * i; j < 1000000; j += i)
                prim[j] = 1;
        }

    int M;
    long long B;
    in >> M;
    for (int i = 0; i < M; ++i) {
        in >> A >> B;

        n = 0;
        card_u = 0;

        for (int prim : prims) {
            if (prim > B) break;
            if (B % prim == 0) {
                divs[n++] = prim;
                while (B % prim == 0) B /= prim;
            }
        }

        if (B > 1) divs[n++] = B;

        for (int j = 1; j <= n; ++j) {
            if (j % 2 == 1) rec(0, j, 1);
            else rec(0, j, -1);
        }

        out << A - card_u << "\n";
    }
}