#include <bits/stdc++.h>
using namespace std;

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

void gen(int pos, int64_t nr, int len, vector<int64_t>& div, int64_t a, int64_t& cnt) {
    if (pos == (int) div.size()) {
        if (nr > 1)
            cnt += (len % 2 ? +1 : -1) * a / nr;
        return;
    }
    gen(pos + 1, nr, len, div, a, cnt);
    gen(pos + 1, nr * div[pos], len + 1, div, a, cnt);
}

int main() {
    int t; fin >> t;
    while (t--) {
        int64_t a, b;
        fin >> a >> b;

        vector<int64_t> div;
        if (b % 2 == 0) {
            div.push_back(2);
            while (b % 2 == 0)
                b /= 2;
        }
        for (int64_t i = 3; i * i <= b; i += 2)
            if (b % i == 0) {
                div.push_back(i);
                while (b % i == 0)
                    b /= i;
            }
        if (b > 1)
            div.push_back(b);

        int64_t cnt = 0;
        gen(0, 1, 0, div, a, cnt);
        fout << a - cnt << '\n';
    }

    fout.close();
    return 0;
}