#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() {
    vector<int64_t> pr;
    vector<bool> sieve(1e6 + 1);

    for (int i = 4; i <= 1e6; i += 2)
        sieve[i] = true;
    for (int i = 3; i * i <= 1e6; i += 2)
        if (!sieve[i])
            for (int j = i * i; j <= 1e6; j += i)
                sieve[j] = true;

    for (int i = 3; i <= 1e6; i += 2)
        if (!sieve[i])
            pr.push_back(i);

    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 (int i = 0; pr[i] * pr[i] <= b; i++)
            if (b % pr[i] == 0) {
                div.push_back(pr[i]);
                while (b % pr[i] == 0)
                    b /= pr[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;
}