#include <bits/stdc++.h>
#define ll long long
#define LMAX 1000000
using namespace std;
ifstream fin("pinex.in");
ofstream fout("pinex.out");
ll t, a, b, rez;
bool fv[LMAX + 2];
vector <ll> prim, divs;

void ciur() {
    for (ll i = 2; i <= LMAX; i += 2) {
        if (fv[i])
            continue;
        prim.push_back(i);
        for (ll j = i * i; j <= LMAX; j += i)
            fv[j] = 1;
        if (i == 2)
            --i;
    }
    return;
}

void multimi(ll pos, ll prod, ll luate) {
    if (pos == divs.size()) {
        if (luate == 0)
            return;
        if (luate % 2 != 0)
            rez += a / prod;
        else
            rez -= a / prod;
        return;
    }
    multimi(pos + 1, prod, luate);
    multimi(pos + 1, prod * divs[pos], luate + 1);
    return;
}

int main() {
    ciur();
    fin >> t;
    while (t--) {
        fin >> a >> b;
        for (int i = 0; i < prim.size() && prim[i] * prim[i] <= b && b > 1; ++i) {
            if (b % prim[i] == 0) {
                divs.push_back(prim[i]);
                while (b % prim[i] == 0)
                    b /= prim[i];
            }
        }
        if (b > 1)
            divs.push_back(b);
        rez = 0;
        if (!divs.empty()) {
            multimi(1, divs[0], 1);
            multimi(1, 1, 0);
            divs.clear();
        }
        fout << a - rez << "\n";
    }
    return 0;
}