#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<long long> 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;
    iota(all(group), 0);
    vector<int> pre(1000001, 1), net(1000001, 998244353);
    vector<vector<int>> n_pri(1000001);
    vector<int> q;
    // for (int j = 0; pri.at(j) <= 1000000; j++)
    // {
    //     for (int i = pri.at(j); i <= 1000000; i += pri.at(j))
    //     {
    //         while (group[i] % pri.at(j) == 0)
    //         {
    //             group[i] /= pri.at(j);
    //         }
    //         group[i] *= pri.at(j);
    //         val[i]++;
    //         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));
    //     }
    // }

    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);
                }
                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 = [&](long long 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)
        {
            dsu t(r);
            map<int, int> mp;
            vector<pair<int, 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];
                    }
                }
                else
                {
                    mp[group[i]] = i;
                    edge.push_back({val[i] + 1, {ttt, i}});
                }
                if (pre[i] >= l)
                {
                    edge.push_back({val[i], {pre[i], i}});
                }
                if (net[i] <= r)
                {
                    edge.push_back({val[i], {net[i], i}});
                }
            }
            sort(all(edge));
            for (auto it : edge)
            {
                int y = t.find(it.second.first);
                int x = t.find(it.second.second);
                if (x != y)
                {
                    t.unite(x, y);
                    ans += it.first;
                }
            }
            cout << ans << "\n";
        }
        else
        {
            dsu t(r);
            vector<pair<long long, pair<long long, long long>>> G;
            for (long long i = l; i <= r; i++)
            {
                for (long long j = l + 1; j <= r; j++)
                {
                    long long 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;
}