#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 (lungime % 2 != 0)
        nr += a / prod;
    else
        nr -= a / prod;
    for (ll j = i + 1; j < divs.size(); ++j)
        submultimi(j, prod * divs[j], lungime + 1);
    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)
                continue;
            divs.push_back(prim[i]);
        }
        for (ll i = 0; i < divs.size(); ++i)
            submultimi(i, divs[i], 1);
        fout << a - nr << "\n";
    }
    return 0;
}