#include<bits/stdc++.h>
#define F(i, a, b) for(int i = a; i <= b; i ++)
#define Fd(i, a, b) for(int i = a; i >= b; i --)
#define int long long
#define pii pair<int, int>
#define fi first
#define se second
#define pb push_back
using namespace std;
const int N = 1e6 + 10;
const int inf = 1e18;
typedef array<int, 3> a3;
int L, R, l[N], r[N], p[N], pr[N], idx = 0, is_prime[N], dis[N], vst[N], cnt[N];
vector<pii> ed[N];
vector<int> a[N];
map<vector<int>, int> mp1, mp2;
void init() {
    int MAX = 1e6;
    p[1] = 1;
    F(i, 2, MAX) {
        if(! p[i]) pr[++ idx] = i, p[i] = i, is_prime[i] = 1, a[i].pb(i);
        for(int j = 1; j <= idx && pr[j] * i <= MAX; j ++) {
            p[i * pr[j]] = pr[j];
            a[i * pr[j]] = a[i];
            if(p[i] == pr[j]) break;
            else a[i * pr[j]].pb(pr[j]);
        }
    }
    F(i, 1, MAX) {
        l[i] = 0;
        int sz = a[i].size();
        F(j, 0, (1 << sz) - 1) {
            vector<int> tmp;
            F(k, 0, sz - 1) if((j >> k) & 1) tmp.pb(a[i][k]);
            l[i] = max(l[i], mp1[tmp]);
        }
        mp1[a[i]] = i;
    }
    Fd(i, MAX, 1) {
        r[i] = MAX + 1;
        int sz = a[i].size();
        F(j, 0, (1 << sz) - 1) {
            vector<int> tmp;
            F(k, 0, sz - 1) if((j >> k) & 1) tmp.pb(a[i][k]);
            r[i] = min(r[i], mp2[tmp]);
        }
        mp2[a[i]] = i;        
    }
}
int prim(int l, int r) {
    int res = 0;
    F(i, l, r) dis[i] = inf, vst[i] = 0, ed[i].clear();
    dis[l] = 0;
    F(i, l, r) F(j, i + 1, r) {
        int w = 0;
        for(auto x : a[i]) w += ! cnt[x] ++;
        for(auto x : a[j]) w += ! cnt[x] ++;
        for(auto x : a[i]) cnt[x] --;
        for(auto x : a[j]) cnt[x] --;
        ed[i].pb({j, w}), ed[j].pb({i, w});
    } 
    F(i, l, r) {
        int u = 0, now = inf;
        F(j, l, r) if(! vst[j] && dis[j] < now) u = j, now = dis[j];
        vst[u] = 1, res += now;
        for(auto [v, w] : ed[u]) dis[v] = min(dis[v], w);
    }
    return res;
}
void sol() {
    cin >> L >> R;
    int flag = 0;
    F(i, L, R) if(is_prime[i]) flag ++;
    if(! flag) {
        cout << prim(L, R) << "\n";
        return;
    }
    vector<int> now;
    F(i, L, R) {
        if(l[i] >= L || r[i] <= R) now.pb(a[i].size());
        else now.pb(a[i].size() + 1);
    }
    int res = 0;
    sort(now.begin(), now.end());
    F(i, 1, now.size()) res += now[i];
    cout << res << "\n";
}
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    init();
    int t; cin >> t;
    F(i, 1, t) sol();
    return 0;
}