#include <bits/stdc++.h>
#define int long long
using namespace std;
bool vis[1000018];
int cnt = 0;
int pri[80000 + 50];
int num[1000018];
void init_pri(int MAXN)
{
    memset(vis, 1, sizeof(vis));
    cnt = 0;
    vis[1] = 0;
    for (int i = 2; i < MAXN; ++i)
    {
        if (vis[i])
        {
            pri[cnt++] = i;
            num[i] = 1;
        }
        for (int j = 0; j < cnt; ++j)
        {
            if (i * pri[j] >= MAXN)
                break;
            vis[i * pri[j]] = 0;
            if (i % pri[j] != 0)
            {
                num[i * pri[j]] = num[i] + 1;
            }
            else
            {
                num[i * pri[j]] = num[i];
            }
            if (i % pri[j] == 0)
                break;
        }
    }
}
bool vs[1000010];
int ct[1000010];
void init_need(int l, int r)
{
    map<int,int> m;
    memset(vs, 1, sizeof(bool) * (r + 10));
    for (int i = l; i <= r; i++)
    {
        int tmp = ct[i];
        if(m[tmp]) continue;
        m[tmp]++;
        for (int j = 0; j <= 1000010; j++)
        {
            if (tmp * j > r)
            {
                break;
            }
            else if (tmp * j >= l and tmp * j <= r and tmp*j!=i)
            {
                vs[tmp * j] = 0;
            }
        }
    }
}
int get_prime_factor(int x)
{
    int i = 2;
    map<int, int> ans;
    while (x > 1 && i * i <= x)
    {
        if (x % i == 0)
        {
            x /= i;
            ans[i--]++;
        }
        i++;
    }
    if (x > 1)
    {
        ans[x]++;
    }
    int as = 1;
    for (auto [o, j] : ans)
    {
        as *= o;
    }
    return as;
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    init_pri(1000010);
//     for (int i = 1; i <= 100; i++)
//     {
//         cout << num[i] << "\n";
//     }
    int T;
    cin >> T;
    while (T--)
    {
        int l, r;
        cin >> l >> r;
        int ans = 0;
        for (int i = l; i <= r; i++)
        {
            ct[i] = get_prime_factor(i);
        }
        init_need(l, r);
//         for (int i = l; i <= r; i++)
//         {
//             cout << i << "\t" << ct[i] << "\t" << vs[i]<<"\t"<<num[i] << endl;
//         }
        for (int i = l; i <= r; i++)
        {
            if (vs[i] == 0)
            {
                ans += num[i];
            }
            else
            {
                ans += (num[i] + 1);
            }
        }
        cout << ans - 2 << endl;
    }
    return 0;
}