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

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

int main() {
    ciur();
    fin >> t;
    while (t--) {
        fin >> a >> b;
        ll nr = 0, prod = 1;
        vector <ll> div;
        for (int i = 0; prim[i] <= b && prim[i] <= a; ++i) {
            if (b % prim[i] != 0)
                continue;
            div.push_back(prim[i]);
        }
        for (int i = 0; i < div.size(); ++i) {
            nr += a / div[i];
            prod *= div[i];
            if (i == div.size())
                continue;
            for (int j = i + 1; j < div.size(); ++j)
                nr -= a / (div[i] * div[j]);
        }
        if (div.size() > 2)
            nr += a / prod;
        fout << a - nr << "\n";
    }
    return 0;
}