#include <bits/stdc++.h>
using namespace std;
#define int long long
#define all(a) a.begin(), a.end()
std::bitset<2000000> not_prime;
class dsu
{
    int n;
    vector<int> pa, size;

public:
    dsu(int x) : n(x), pa(x + 1), size(x + 1, 1)
    {
        iota(all(pa), 0);
    }
    int find(int x)
    {
        return pa[x] == x ? x : find(pa[x]);
    }
    void unite(int x, int y)
    {
        x = find(x), y = find(y);
        if (x == y)
        {
            return;
        }
        if (size[x] < size[y])
        {
            swap(x, y);
        }
        pa[y] = x;
        size[x] += size[y];
    }
};
class prime
{
public:
    std::vector<int> pri = {2};
    void build(int n)
    {
        for (int i = 3; i * i <= n; i += 2)
        {
            if (!not_prime[i])
            {
                for (int j = i * i; j < n; j += i)
                {
                    not_prime[j] = 1;
                }
            }
        }
        for (int i = 3; i <= n; i += 2)
        {
            if (!not_prime[i])
            {
                pri.push_back(i);
            }
        }
    }
    prime(int n)
    {
        build(n);
    }
    bool is_pri(int x)
    {
        if (x % 2 == 0)
        {
            return false;
        }
        return !not_prime[x];
    }
    int at(int n)
    {
        return pri[n];
    }
};
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int test = 1;
    cin >> test;
    prime pri(1 << 20);
    vector<int> val(1000001);
    vector<int> group = val;
    vector<int> pre(1000001), net(1000001, 998244353);
    vector<vector<int>> n_pri(1000001);
    vector<int> q;
    for (int i = 1; i <= 1000000; i++)
    {
        int t = i;
        int tmp = 1;
        for (int j = 0; pri.at(j) * pri.at(j) <= t; j++)
        {
            if (t % pri.at(j) == 0)
            {
                val[i]++;
                tmp *= pri.at(j);
                int cntn = n_pri[i].size();
                for (int k = 0; k < cntn; k++)
                {
                    int x = n_pri[i][k] * pri.at(j);
                    n_pri[i].emplace_back(x);
                }
                n_pri[i].emplace_back(pri.at(j));
                while (t % pri.at(j) == 0)
                {
                    t /= pri.at(j);
                }
            }
        }
        if (t != 1)
        {
            val[i]++;
            tmp *= t;
            int cntn = n_pri[i].size();
            for (int j = 0; j < cntn; j++)
            {
                int x = n_pri[i][j] * t;
                n_pri[i].emplace_back(x);
            }
            n_pri[i].emplace_back(t);
        }
        group[i] = tmp;
    }
    auto get_val = [&](int x)
    {
        int ans = 0;
        for (int j = 0; pri.at(j) * pri.at(j) <= x; j++)
        {
            if (x % pri.at(j) == 0)
            {
                ans++;
                while (x % pri.at(j) == 0)
                {
                    x /= pri.at(j);
                }
            }
        }
        if (x != 1)
        {
            ans++;
        }
        return ans;
    };
    vector<int> mp(1000001, 1);
    for (int i = 1; i <= 1000000; i++)
    {
        for (auto it : n_pri[i])
        {
            pre[i] = max(pre[i], mp[it]);
        }
        mp[group[i]] = i;
    }
    mp = net;
    for (int i = 1000000; i > 0; i--)
    {
        for (auto it : n_pri[i])
        {
            net[i] = min(net[i], mp[it]);
        }
        mp[group[i]] = i;
    }

    while (test--)
    {
        int ans = 0;
        int l, r;
        cin >> l >> r;
        if (l == 1)
        {
            for (int i = l; i <= r; i++)
            {
                ans += val[i];
            }
            cout << ans << '\n';
            continue;
        }

        int ttt = *lower_bound(all(pri.pri), l);
        if (ttt <= r)
        {
            int cnt = 0;
            dsu t(r);
            map<int, int> mp;
            vector<pair<int, int>> edge;
            for (int i = l; i <= r; i++)
            {
                if (mp.count(group[i]))
                {
                    int x = t.find(i), y = t.find(mp[group[i]]);
                    if (x != y)
                    {
                        t.unite(x, y);
                        ans += val[i];
                        cnt++;
                    }
                }
                else
                {
                    mp[group[i]] = i;
                }
                edge.emplace_back(val[i], i);
            }
            sort(all(edge));
            for (auto it : edge)
            {
                if (pre[it.second] >= l)
                {
                    int y;
                    y = t.find(pre[it.second]);
                    int x = it.second;
                    x = t.find(x);
                    if (x != y)
                    {
                        cnt++;
                        t.unite(x, y);
                        ans += val[it.second];
                    }
                }
                if (net[it.second] <= r)
                {
                    int y;
                    int x = t.find(it.second);
                    y = t.find(net[it.second]);
                    if (x != y)
                    {
                        cnt++;
                        t.unite(x, y);
                        ans += val[it.second];
                    }
                }
            }
            for (auto it : edge)
            {
                int y;
                int x = t.find(it.second);
                y = t.find(ttt);
                if (x != y)
                {
                    cnt++;
                    t.unite(x, y);
                    ans += val[it.second] + 1;
                }
            }
            cout << ans << "\n";
            // cerr << cnt << "\n";
        }
        else
        {
            dsu t(r);
            vector<pair<int, pair<int, int>>> G;
            for (int i = l; i <= r; i++)
            {
                for (int j = l + 1; j <= r; j++)
                {
                    int tmp;
                    if (lcm(i, j) <= 1000000)
                    {
                        tmp = val[lcm(i, j)];
                    }
                    else
                    {
                        tmp = get_val(lcm(i, j));
                    }

                    G.push_back({tmp, {i, j}});
                }
            }
            sort(all(G));
            for (auto it : G)
            {
                auto [x, y] = it.second;
                x = t.find(x);
                y = t.find(y);
                if (x == y)
                {
                    continue;
                }
                else
                {
                    ans += it.first;
                    t.unite(x, y);
                }
            }
            cout << ans << "\n";
        }
    }
    return 0;
}