#include <fstream>
#include <vector>
#define DEF 1000010

using namespace std;

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

int t;

long long a, b;

bool C[DEF];

vector < int > P;

void back (int i, int nr, long long prod, long long & sol, vector < long long > & D);

int main () {
    fin >> t;
    C[1] = 1;
    for (int i = 2; i <= DEF - 1; ++ i) {
        if (!C[i]) {
            P.push_back (i);
            for (int j = 2; j * i <= DEF - 1; ++ j) {
                C[i * j] = 1;
            }
        }
    }

    for (; t; -- t) {
        fin >> a >> b;

        long long sol = 0;
        vector < long long > D;

        for (int i = 0; i < P.size () and P[i] * P[i] <= b; ++ i) {
            if (b % P[i] == 0) {
                D.push_back (P[i]);
                while (b % P[i] == 0) {
                    b /= P[i];
                }
            }
        }
        if (b > 1)
            D.push_back (b);

        back (0, 0, 1, sol, D);

        fout << sol << '\n';

        D.clear ();
    }

    return 0;
}

void back (int i, int nr, long long prod, long long & sol, vector < long long > & D) {
    if (i == D.size ()) {
        sol += (nr % 2) ? (- a / prod) : (a / prod);
        return;
    }
    back (i + 1, nr, prod, sol, D);
    back (i + 1, nr + 1, prod * D[i], sol, D);
}