#pragma GCC optimize(2)
#pragma GCC optimize(3)
#include <bits/stdc++.h>

struct DSU {
    std::vector<int> f, siz;
    
    DSU() {}
    DSU(int n) {
        init(n);
    }
    
    void init(int n) {
        f.resize(n);
        std::iota(f.begin(), f.end(), 0);
        siz.assign(n, 1);
    }
    
    int find(int x) {
        while (x != f[x]) {
            x = f[x] = f[f[x]];
        }
        return x;
    }
    
    bool same(int x, int y) {
        return find(x) == find(y);
    }
    
    bool merge(int x, int y) {
        x = find(x);
        y = find(y);
        if (x == y) {
            return false;
        }
        siz[x] += siz[y];
        f[y] = x;
        return true;
    }
    
    int size(int x) {
        return siz[find(x)];
    }
};

void solve(){
    int l, r;
    std::cin >> l >> r;
    DSU dsu(r + 1);
    int o = r - l + 1;

    auto upd = [](std::vector<std::pair<int, int> > &a, std::pair<int, int> b) {
        // 维护first的前2小，并且second不相同, 并且前2小的second不同
        auto c = std::min({a[0], a[1], b});
        std::pair<int, int> d = {1e3, 1e3};
        if (b.second != c.second) {
            d = std::min(d, b);
        }
        for (int i = 0; i < 2; i += 1) {
            if (a[i].second != c.second) {
                d = std::min(d, a[i]);
            }
        }
        a[0] = c;
        a[1] = d;
    };

    std::vector<int> is_prime(r + 1, 1);
    std::vector<int> cnt(r + 1);

    std::vector factor(r + 1, std::vector<int>());

    for (int i = 2; i <= r; i += 1) {
        if (is_prime[i]) {
            for (int j = i; j <= r; j += i) {
                is_prime[j] = 0;
                cnt[j] += 1;
                factor[j].emplace_back(i);
            }
        }
    }
    
    
    int res = 0;
    int t = 0;
    std::vector dp(r + 1, std::vector<std::pair<int, int> >(2, {1e3, 1e3}));
    std::vector<std::pair<int, int> > go(r + 1, {1e3, 1e3});
    while(o > 1) {
        for (int i = 0; i <= r; i += 1) {
            go[i] = {1e3, 1e3};
            dp[i][0] = dp[i][1] = {1e3, 1e3};
        }
        t += 1;
        for (int i = 1; i <= r; i += 1) {
            for (int j = i; j <= r; j += i) {
                if (j < l) continue;
                upd(dp[i], std::make_pair(cnt[j] - cnt[i], dsu.find(j)));
            }
        }
        for (int i = l; i <= r; i += 1) {
            std::pair<int, int> x = {1e9, 1e9};

            std::function<void(int, int) > dfs = [&](int u, int g) {
                if (u == factor[i].size()) {
                    if (dsu.find(i) != dp[g][0].second)
                        x = std::min(x, dp[g][0]);
                    if (dsu.find(i) != dp[g][1].second)
                        x = std::min(x, dp[g][1]);
                    return;
                }
                dfs(u + 1, g);
                dfs(u + 1, g * factor[i][u]);
            };
            dfs(0, 1);
            go[dsu.find(i)] = std::min(go[dsu.find(i)], 
                        {x.first + cnt[i], x.second});
        }
        for (int i = l; i <= r; i += 1) {
            int x = dsu.find(i);
            int y = go[x].second;
            if (dsu.find(i) != i) continue;
            if (dsu.merge(x, y)) {
                res += go[x].first;
                o -= 1;
            }
        }
    }
    // std::cout << t << "\n";
    std::cout << res << "\n";
}

int main(){
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    int T;
    std::cin >> T;
    // double start_time = clock();
    while(T--) solve();
    // std::cout << (clock() - start_time) / 1000000 << "\n";
    return 0;
}