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

using namespace std;

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

vector<int> prims;

long A;
long card_u;

void rec(const vector<int>& divs, int pos, int left, long res) {
    if (pos == divs.size()) {
        if (!left) card_u += A / res;
        return;
    }
    if (!left) {
        card_u += A / res;
        return;
    }

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

int main() {
    prims.push_back(2);
    for (int i = 3; i <= 1000000; ++i) {
        bool prim = true;
        for (int j = 2; j <= sqrt(i)+1; ++j)
            if (i % j == 0) {
                prim = false;
                break;
            }
        
        if (prim) prims.push_back(i);
    }

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

        vector<int> divs;
        for (int prim : prims) {
            if (prim > B) break;
            if (B % prim == 0) divs.push_back(prim);
        }

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

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