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

template<class F, class S>
ostream &operator<<(ostream &s, const pair<F, S> &v) {
    s << "(" << v.first << ", " << v.second << ")";
    return s;
}
template<ranges::range T> requires (!is_convertible_v<T, string_view>)
istream &operator>>(istream &s, T &&v) { 
    for (auto &&x : v) s >> x; 
    return s; 
}
template<ranges::range T> requires (!is_convertible_v<T, string_view>)
ostream &operator<<(ostream &s, T &&v) { 
    for (auto &&x : v) s << x << ' '; 
    return s; 
}
 
#ifdef LOCAL
template<class... T> void dbg(T... x) {
    char e{};
    ((cerr << e << x, e = ' '), ...);
}
#define debug(x...) dbg(#x, '=', x, '\n')
#else
#define debug(...) ((void)0)
#endif
 
#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()
#define ff first
#define ss second
 
template<class T> inline constexpr T inf = numeric_limits<T>::max() / 2;
bool chmin(auto &a, auto b) { return (b < a and (a = b, true)); }
bool chmax(auto &a, auto b) { return (a < b and (a = b, true)); }
 
using u32 = unsigned int;
using i64 = long long;
using u64 = unsigned long long;
using i128 = __int128;
using u128 = unsigned __int128;

constexpr i64 mod = 998244353;
constexpr i64 inv2 = (mod + 1) / 2;

vector<int> primes;
vector<int> isp, pset;
vector<int> pcnt, W;
void sieve(int n) {
    isp.assign(n + 1, true);
    pset.assign(n + 1, 1);
    pcnt.assign(n + 1, 0);
    W.assign(n + 1, 0);
    isp[0] = false;
    pcnt[1] = 1;
    for (int i = 2; i <= n; i++) {
        if (isp[i]) {
            primes.push_back(i);
            pcnt[i] = 1;
            pset[i] = i;
            W[i] = 1;
        }
        pcnt[i] += pcnt[i - 1];
        for (i64 p : primes) {
            if (p * i > n) {
                break;
            }
            isp[i * p] = false;
            pset[i * p] = pset[i] * p;
            W[i * p] = W[i] + 1;
            if (i % p == 0) {
                W[i * p] -= 1;
                pset[i * p] /= p;
                break;
            }
        }
    }
}

struct DSU {
    vector<int> f;
    DSU(int n) : f(n, -1) {}
    int find(int x) { return f[x] < 0 ? x : f[x] = find(f[x]); }
    bool merge(int x, int y) {
        x = find(x);
        y = find(y);
        if (x == y) {
            return false;
        }
        f[x] = y;
        return true;
    }
};

const int N = 1E6;

vector<pair<int, int>> E[16];

void solve() {
    int l, r;
    cin >> l >> r;

    if (pcnt[r] == pcnt[l - 1]) {
        for (int w = 0; w <= 15; w++) {
            E[w].clear();
        }
        for (int x = l; x <= r; x++)
            for (int y = x + 1; y <= r; y++) {
                E[W[x] + W[y] - W[gcd(x, y)]].push_back({x, y});
            }
        DSU dsu(r + 1);
        int ans = 0;
        for (int w = 0; w <= 15; w++) {
            for (auto [x, y] : E[w]) {
                if (dsu.merge(x, y)) {
                    ans += w;
                }
            }
        }
        cout << ans << '\n';
    } else {
        int ans = 0;
        vector<bool> use(r + 1), out(r + 1);
        for (int x = l; x <= r; x++) {
            int s = pset[x];
            if (use[s]) {
                continue;
            }
            use[s] = true;
            for (int y = (l + s - 1) / s * s; y <= r; y += s) {
                if (!out[y] and pset[y] % s == 0 and y != x) {
                    out[y] = true;
                    ans += W[y];
                }
            }
        }
        bool ok = false;
        for (int x = l; x <= r; x++) {
            if (out[x]) {
                continue;
            }
            if (isp[x] and !ok) {
                ok = true;
            } else {
                ans += W[x] + 1;
            }
        }
        cout << ans << '\n';
    }
}

signed main() {
    cin.tie(0)->sync_with_stdio(0);
    cin.exceptions(cin.failbit);

    sieve(N);

    int t = 1;
    cin >> t;
    
    while (t--) {
        solve();
    }
    
    return 0;
}

answer.code:10:10: error: ‘ranges’ has not been declared
   10 | template<ranges::range T> requires (!is_convertible_v<T, string_view>)
      |          ^~~~~~
answer.code:10:24: error: expected ‘>’ before ‘T’
   10 | template<ranges::range T> requires (!is_convertible_v<T, string_view>)
      |                        ^
answer.code:10:36: error: expected constructor, destructor, or type conversion before ‘(’ token
   10 | template<ranges::range T> requires (!is_convertible_v<T, string_view>)
      |                                    ^
answer.code:15:10: error: ‘ranges’ has not been declared
   15 | template<ranges::range T> requires (!is_convertible_v<T, string_view>)
      |          ^~~~~~
answer.code:15:24: error: expected ‘>’ before ‘T’
   15 | template<ranges::range T> requires (!is_convertible_v<T, string_view>)
      |                        ^
answer.code:15:36: error: expected constructor, destructor, or type conversion before ‘(’ token
   15 | template<ranges::range T> requires (!is_convertible_v<T, string_view>)
      |                                    ^
answer.code:36:19: warning: inline variables are only available with ‘-std=c++17’ or ‘-std=gnu++17’ [-Wc++17-extensions]
   36 | template<class T> inline constexpr T inf = numeric_limits<T>::max() / 2;
      |                   ^~~~~~
answer.code:37:12: warning: use of ‘auto’ in parameter declaration only available with ‘-std=c++20’ or ‘-fconcepts’
   37 | bool chmin(auto &a, auto b) { return (b < a and (a = b, true)); }
      |            ^~~~
answer.code:37:21: warning: use of ‘auto’ in parameter declaration only available with ‘-std=c++20’ or ‘-fconcepts’
   37 | bool chmin(auto &a, auto b) { return (b < a and (a = b, true)); }
      |                     ^~~~
answer.code:38:12: warning: use of ‘auto’ in parameter declaration only available with ‘-std=c++20’ or ‘-fconcepts’
   38 | bool chmax(auto &a, auto b) { return (a < b and (a = b, true)); }
      |            ^~~~
answer.code:38:21: warning: use of ‘auto’ in parameter declaration only available with ‘-std=c++20’ or ‘-fconcepts’
   38 | bool chmax(auto &a, auto b) { return (a < b and (a = b, true)); }
      |                     ^~~~
answer.code: In function ‘void solve()’:
answer.code:112:35: error: ‘gcd’ was not declared in this scope
  112 |                 E[W[x] + W[y] - W[gcd(x, y)]].push_back({x, y});
      |                                   ^~~
answer.code:117:23: warning: structured bindings only available with ‘-std=c++17’ or ‘-std=gnu++17’ [-Wc++17-extensions]
  117 |             for (auto [x, y] : E[w]) {
      |                       ^