#include <fstream>
#include <vector>
using namespace std;

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

typedef unsigned long long ull;

const int N = 1e6 + 5;

ull a, b, sol;
int n;
vector <ull> v, prim;
vector <bool> phi(N, 0);

void precalc() {
    prim.push_back (2);
    for (int i = 4; i < N; i +=2)
        phi[i] = 1;
    int i = 3;
    for (; i < N / 2; i += 2)
        if (!phi[i]) {
            prim.push_back (i);
            for (int j = i * 3; j < N; j += i * 2)
                phi[j] = 1;
        }
    for (; i < N; ++i)
        if (!phi[i])
            prim.push_back (i);
}

int main() {
    precalc();
    fin >> n;
    for (int i = 0; i < n; ++i) {
        vector <ull>().swap (v);
        fin >> a >> b;
        ull aux = b;
        for (int j = 0; i < prim.size() && 1LL * prim[j] * prim[j] <= aux && b != 1; ++j)
            if (b % prim[j] == 0) {
                v.push_back (prim[j]);
                while (b % prim[j] == 0)
                    b /= prim[j];
            }
        if (b != 1)
            v.push_back (b);
        sol = 0;
        int k = v.size();
        for (int i = 1; i < (1 << k); ++i) {
            ull prod = 1, nr = 0;
            for (int j = 0; j < k; ++j)
                if (i & (1 << j)) {
                    prod *= v[j];
                    nr++;
                }
            if (nr % 2)
                sol += a / prod;
            else
                sol -= a / prod;
        }
        fout << a - sol << "\n";
    }
}