#include <bits/stdc++.h>

using namespace std;
#define int long long
const int N = 1e6 + 10;
const int mod = 998244353;
using i64 = int64_t;
int l1[N], r1[N];
vector<int> pri;
int isp[N];
int cnt = 0;
int fa[N];
int w[N];

int find(int x) {
    if (fa[x] == x)return x;
    return fa[x] = find(fa[x]);
}

void getprime() {
    for (int i = 2; i < N - 5; i++)isp[i] = i;
    for (int i = 2; i < N - 5; i++) {
        if (isp[i] == i) {
            pri.push_back(i);
            cnt++;
        }
        for (int j = 0; j < cnt && 1LL * pri[j] * i < N - 5; j++) {
            isp[pri[j] * i] = pri[j];
            if (i % pri[j] == 0) break;
        }
    }
}

int gcd(int a, int b) {
    if (b == 0)return a;
    return gcd(b, a % b);
}


void solve() {
    int l, r;
    cin >> l >> r;
    if (l == r) {
        cout << 0 << '\n';
        return;
    }
    for (int i = l; i <= r; i++)fa[i] = i;
    auto y = std::lower_bound(pri.begin(), pri.end(), l);
    vector<vector<array<int, 2>>> a(15);
    if (*y <= r) {
        int yy = *y;
        for (int i = l; i <= r; i++) {
            if (i % yy == 0) {
                a[w[i]].push_back({i, yy});
            } else {
                a[w[i] + 1].push_back({i, yy});
            }

            if (l1[i] >= l) {
                a[w[i]].push_back({l1[i], i});
            }
            if (r1[i] <= r) {
                a[w[r1[i]]].push_back({r1[i], i});
            }
        }
    } else {
        for (int i = l; i <= r; i++) {
            for (int j = l + 1; j <= r; j++) {
                a[w[lcm(i, j)]].push_back({i, j});
            }
        }
    }
    int ans = 0;
    int num = 0;
    for (int i = 1; i < 15; i++) {
        for (int j = 0; j < a[i].size(); j++) {
            auto y = a[i][j];
            int a1 = find(y[0]), a2 = find(y[1]);
            if (a1 == a2)continue;
            ans += i;
            fa[a1] = a2;
            //   cout<<a1<<" "<<a2<<'\n';
            num++;
            if (num == r - l) {
                cout << ans << "\n";
                return;
            }
        }
    }


}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);
    //cout<<fixed<<setprecision(3);
    int T = 1;
    cin >> T;
    for (int i = 1; i <= N - 5; i++) {
        l1[i] = 1;
        r1[i] = 1e9;
    }
    getprime();
    vector<vector<int>> px(1000005);
    int ans = 0;
    for (int i = 2; i <= N - 8; i++) {
        int x = i;
        int y = 0;
        int num = 0;
        while (x != 1) {
            if (isp[x] != y) {
                num++;
                px[isp[x]].push_back(i);
            }
            y = isp[x];
            x /= isp[x];
        }
        w[i] = num;
        ans += w[i];
        //  cout<<w[i]<<" ";
    }
    for (int i = 2; i <= N - 8; i++) {
        if (px[i].size() == 0)continue;
        sort(px[i].begin(), px[i].end());
        for (int j = 1; j < px[i].size(); j++) {
            r1[px[i][j - 1]] = min(r1[px[i][j - 1]], px[i][j]);
            l1[px[i][j]] = max(px[i][j - 1], l1[px[i][j]]);
        }
    }
    for (int i = 2; i <= 6125; i++) {
       cout<<l1[i]<<" "<<r1[i]<<" "<<i<<'\n';
    }
    while (T--) solve();
    return 0;
}