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

using pii = pair<int, int>;
const int N = 1e6 + 1;

int pf[N], w[N];
vector<int> primes;

vector<int> factors[N];
vector<int> nxt[N];

int cost[N], ctz[1 << 16];
bool vis[N];

struct smallpq{
    vector<int> item[16];
    int cnt = 0, msk = 0; 
    void push(const pii &a) {
        item[a.first].push_back(a.second);
        msk |= 1 << a.first;
        cnt ++;
    }
    int size() {return cnt;}
    pii top() {
        int ptr = ctz[msk];
        return {ptr, item[ptr].back()};
    }
    void pop() {
        int ptr = ctz[msk];
        item[ptr].pop_back();
        cnt --;
        if(item[ptr].empty()) msk ^= (1 << ptr);
    }
} q;

int solve() {
    int L, R;
    cin >> L >> R;

    for(int i = L + 1; i <= R; i ++)
        vis[i] = false;


    for(int i = 2; i <= R; i ++) {
        nxt[i].clear();
        for(int j = i; j <= R; j += i)
            if(j > L) q.push({w[j], j});
        while(q.size()) {
            nxt[i].push_back(q.top().second);
            q.pop();
        }
        reverse(nxt[i].begin(), nxt[i].end());
        cost[i] = L % i == 0 ? w[L] - w[i] : w[L];
    }
    
    for(int i = 2; i <= R; i ++)
        if(nxt[i].size()) q.push({w[nxt[i].back()] + cost[i], i});

    int ans = 0;

    while(q.size()) {
        auto [c, p] = q.top();
        q.pop();

        if(nxt[p].empty() || c != cost[p] + w[nxt[p].back()]) continue;

        int tar = -1;

        if(!vis[nxt[p].back()]) {
            vis[nxt[p].back()] = true;
            tar = nxt[p].back();
            ans += c;
        }

        while(nxt[p].size() && vis[nxt[p].back()])
            nxt[p].pop_back();
        
        if(nxt[p].size()) q.push({w[nxt[p].back()] + cost[p], p});
        
        if(tar > 0)
            for(auto fc : factors[tar])
                if(cost[fc] > w[tar] - w[fc]) {
                    cost[fc] = w[tar] - w[fc];
                    if(nxt[fc].size()) q.push({w[nxt[fc].back()] + cost[fc], fc});
                }
    }

    return ans;
}

int main() {
    for(int i = 2; i < N; i ++) {
        if(!pf[i]) {
            pf[i] = i;
            w[i] = 1;
            primes.push_back(i);
        }
        for(int j : primes) {
            if(i * (long long)j >= N) break;
            pf[i * j] = j;
            w[i * j] = w[i];
            if(i % j == 0) break;
            w[i * j] ++;
        }
    }

    for(int i = 2; i < N; i ++)
        for(int j = i; j < N; j += i)
            factors[j].push_back(i);
    

    for(int i = 0; i < 16; i ++)
        ctz[1 << i] = i;
    
    for(int i = 1; i < (1 << 16); i ++)
        ctz[i] = ctz[i & -i];

    ios::sync_with_stdio(false);
    cin.tie(0);

    int T;
    cin >> T;
    while(T --)
        cout << solve() << "\n";
}