#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;

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;
        nr = 0;
        vector <ll> div;
        for (ll i = 0; prim[i] <= b && prim[i] <= a && i < prim.size(); ++i) {
            if (b % prim[i] != 0)
                continue;
            div.push_back(prim[i]);
        }
        bool nxt[div.size() + 5], semn = true;
        for (ll i = 1; i <= div.size(); ++i) {
            for (ll j = div.size(); j >= 1; --j) {
                if (j >= div.size() - i + 1)
                    nxt[j] = 1;
                else
                    nxt[j] = 0;
            }
            do {
                ll prod = 1;
                for (ll j = 1; j <= div.size(); ++j) {
                    if (nxt[j] == 1)
                        prod *= div[j - 1];
                }
                if (semn)
                    nr += a / prod;
                else
                    nr -= a / prod;
            } while (next_permutation(nxt + 1, nxt + div.size() + 1));
            if (semn)
                semn = false;
            else
                semn = true;
        }
        fout << a - nr << "\n";
    }
    return 0;
}