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

using namespace std;

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

int t;

long long a, b;

bool C[DEF];

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

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

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

        int sol = 0;
        vector < int > D;

        for (int i = 2; i * i <= b; ++ i) {
            if (i % b == 0 and !C[i]) {
                D.push_back (i);
            }
        }

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

        fout << sol << '\n';

        D.clear ();
    }

    return 0;
}

void back (int i, int nr, int prod, int & sol, vector < int > & 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);
}