#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, nr, fv[LMAX];
vector <ll> prim, divs;

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

void submultimi(ll i, ll prod, ll lungime) {
    if (i == divs.size() - 1) {
        if (lungime % 2 != 0 && lungime > 0)
            nr += a / prod;
        else if (lungime > 0)
            nr -= a / prod;
        return;
    }
    submultimi(i + 1, prod * divs[i + 1], lungime + 1);
    submultimi(i + 1, prod, lungime);
    return;
}

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