#include<bits/stdc++.h>
#define all(x) begin(x), end(x)
using namespace std;
using ll = long long;
struct DSU {
    vector<int> e;
    DSU(int n) : e(n, -1) {}
    int find(int v) { return e[v] < 0 ? v : e[v] = find(e[v]); }
    bool join(int u, int v) {
        u = find(u), v = find(v);
        if(u == v) return 0;
        if(-e[u] < -e[v]) swap(u, v);
        e[u] += e[v];
        e[v] = u;
        return 1;
    }
};

const int L = 1<<20;
int w[L];
int main() {
    cin.tie(0)->sync_with_stdio(0);
    for(int x = 2; x < L; x++) {
        int ok = 1;
        for(int y = 2; ok && y * y <= x; y++) {
            if(x % y == 0) ok = 0;
        }
        if(ok) {
            for(int j = x; j < L; j += x)
                w[j]++;
        }
    }
    int T;
    cin >> T;
    while(T--) {
        int l, r;
        cin >> l >> r;
        vector<array<int, 3>> edges;
        for(int x = 1; x <= r; x++) {
            array<int, 2> cheapest {1<<30, 1<<30};
            for(int y = x; y <= r; y += x) if(y >= l) {
                cheapest = min(cheapest, {w[y], y});
            }
            for(int y = x; y <= r; y += x) if(y >= l) {
                edges.push_back({w[y] + cheapest[0] - w[x], cheapest[1], y});
            }
        }
        sort(all(edges));
        DSU D(r + 1);
        ll ans = 0;
        for(auto [cost, x, y] : edges)  {
            int t = D.join(x, y);
            ans += cost * t;
            // if(t) cout << x << " " << y << " add " << cost << endl;
        }
        cout << ans << '\n';
    }
}