#include <bits/stdc++.h>
using namespace std;

#define fi first
#define se second
#define pb push_back
#define Mp make_pair
#define SZ(x) (int((x).size()))

typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;

constexpr int N = 1000100;

int v[N], p[N], m;
void solve() {
    v[1] = 1;
    int l, r;
    cin >> l >> r;

    ll ans = 0;
    set<int> st;
    for(int i = l; i <= r; i++) {
        vi pr; int x = 1;
        for(int j = i; j > 1; j /= v[j])
            if(SZ(pr) && pr.back() != v[j]) pr.pb(v[j]), x *= v[j];
            else if(!SZ(pr)) pr.pb(v[j]), x *= v[j];
        if(st.find(x) == st.end()) st.insert(x);
        else ans += SZ(pr);
    }
    
    vi nums;
    for(auto x : st) nums.pb(x);

    if(SZ(nums) <= 1e3) {
        vector<array<int, 3>> edges;
        v[1] = 1e9;
        for(int i = 0; i < SZ(nums); i++) {
            for(int j = i + 1; j < SZ(nums); j++) {
                int x = nums[i], y = nums[j];
                int ans = 0;
                while(x > 1 || y > 1){
                    if(v[x] == v[y]){
                        ans++;
                        x /= v[x], y /= v[y];
                    }
                    else{
                        ans++;
                        if(v[x] < v[y]) x /= v[x];
                        else y /= v[y];
                    }
                }
                edges.pb({ans, i, j});
            }
        }
        sort(edges.begin(), edges.end());
        vi f(SZ(nums));
        iota(f.begin(), f.end(), 0);
        function<int(int)> find = [&](int x) {
            return f[x] == x ? x : f[x] = find(f[x]);
        };
        for(auto [val, i, j] : edges) {
            int x = find(i), y = find(j);
            if(x != y) {
                f[x] = y;
                ans += val;
            }
        }
        cout << ans << '\n';
        return;
    }

    vi prcnt(r + 1);
    for(int x : nums) {
        vi pr;
        for(int j = x; j > 1; j /= v[j])
            pr.pb(v[j]);
        prcnt[x] = SZ(pr);
    }
    sort(nums.begin(), nums.end(), [&](int x, int y) {
        return prcnt[x] < prcnt[y];
    });

    vi f(r + 1, 1e9);
    for(int i = 0; i < SZ(nums); i++) {
        int x = nums[i];
        vi pr, vals, cnt;
        for(int j = x; j > 1; j /= v[j])
            pr.pb(v[j]);
        function<void(int, int, int)> dfs = [&](int x, int nw, int c) {
            if(x == SZ(pr)) {
                vals.pb(nw);
                cnt.pb(c);
                return;
            }
            dfs(x + 1, nw, c);
            dfs(x + 1, nw * pr[x], c + 1);
        };
        dfs(0, 1, 0);
        if(i) {
            int now = 1e9;
            for(auto v : vals) {
                now = min(now, f[v] + SZ(pr));
            }
            // cout << "       " << now << '\n';
            ans += now;
        }
        for(int j = 0; j < SZ(vals); j++) {
            f[vals[j]] = min(f[vals[j]], SZ(pr) - cnt[j]);
        }
    }
    cout << ans << '\n';
}
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    v[1] = 1;
    for(int i = 2; i <= 1e6; i++) {
        if(!v[i]) v[i] = i, p[++m] = i;
        for(int j = 1; j <= m && p[j] * i <= 1e6; j++) {
            v[i * p[j]] = p[j];
            if(v[i] == p[j]) break;
        }
    }
    int t = 1;
    cin >> t;
    while(t--) solve();
    return 0;
}