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

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

//<ciur>
#define MAXP 1000010
#define NUMP 80000
bitset <MAXP> p;
vector<int64_t> prim;

void ciur()
{
    for (int i = 1; ((i * i) << 1) + (i << 1) < MAXP; ++i) {
        if (!p[i]) {
            for (int j = ((i * i) << 1) + (i << 1); (j << 1) + 1 <= MAXP; j += (i << 1) + 1) {
                p[j] = true;
            }
        }
    }

    prim.push_back(2);
    for (int i = 1; (i << 1) < MAXP; ++i) {
        if (!p[i]) {
            prim.push_back((i << 1) + 1);
        }
    }
}
//</ciur>

void do_test()
{
    int64_t a, b;
    f >> a >> b;

    vector<int64_t> fp;

    int d = 0;
    while (b > 1) {
        if (b % prim[d] == 0) {
            fp.push_back(prim[d]);

            while(b % prim[d] == 0) {
                b /= prim[d];
            }
        }
        if (prim[d] * prim[d] > b && b > 1) {
            fp.push_back(b);
            break;
        }

        d++;
    }

    int n = fp.size();
    int64_t sol = a;

    for (int i = 1; i < (1 << n); i++) {
        int64_t nr = 1, nf = 0;

        for (int k = 0; k < n; k++) {
            if (i & (1 << k)) {
                nr *= fp[k];
                nf++;
            }
        }

        if (nf & 1 == 1) {
            sol = sol - (int64_t)a / nr;
        } else {
            sol = sol + (int64_t)a / nr;
        }
    }

    g << sol << '\n';
}

int main()
{
    ciur();

    int m;
    f >> m;

    for (int i = 1; i <= m; i++) {
        do_test();
    }

    f.close();
    g.close();
    return 0;
}