#pragma GCC optimize(2)
#pragma GCC optimize(3,"Ofast","inline")
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 1e6 + 10;
int vis[N];
vector<int> pri;

void init(int n){
    vis[1] = 1;
    for(int i = 2; i <= N - 10; i++){
        if(!vis[i]) vis[i] = i, pri.push_back(i);
        for(int j = 0; i * pri[j] <= N - 10 && j < pri.size(); j++){
            vis[i * pri[j]] = pri[j];
            if(i % pri[j] == 0) break;
        }
    }
}

int ne_l, ne_r, sz, down, up;

void cal_l(int u, int sum, vector<int>& ob){
    if(u == sz){
        if(sum >= down && (ne_l == down - 1 || ne_l <= sum)){
            ne_l = sum;
        }
        return ;
    }
    for(int i = 1; i <= 21; i++){
        cal_l(u + 1, sum, ob);
        if(ll(sum) * ob[u] >= up) break;
        sum = sum * ob[u];
    }
}

void cal_r(int u, int sum, vector<int>& ob){
    if(u == sz){
        if(sum > down && (ne_r == up + 1 || ne_r >= sum)){
            ne_r = sum;
        }
        return ;
    }
    for(int i = 1; i <= 21; i++){
        cal_r(u + 1, sum, ob);
        if(ll(sum) * ob[u] > up) break;
        sum = sum * ob[u];
    }
}

void solve(){
    int l, r; cin >> l >> r;
    if(l == r){
        cout << 0 << '\n'; return ;
    }
    if(r - l + 1 <= 400){
        set<int> st[r - l + 2];
        for(int i = l; i <= r; i++){
            int num = i, lst = 0;
            while(num != 1){
                if(lst != vis[num]) st[i - l + 1].insert(vis[num]), lst = vis[num];
                num = num / vis[num];
            }
            //cout << i << ' ' << st[i - l + 1].size() << '\n';
        }
        vector<array<ll, 3>> e;
        for(int i = l; i <= r; i++){
            for(int j = i + 1; j <= r; j++){
                int idx = 0;
                for(auto it : st[i - l + 1]){
                    if(st[j - l + 1].find(it) != st[j - l + 1].end()){
                        idx += 1;
                    }
                }
                int cnt = st[i - l + 1].size() + st[j - l + 1].size() - idx;
                e.push_back({i - l + 1, j - l + 1, cnt});
                e.push_back({j - l + 1, i - l + 1, cnt});
            }
        }
        sort(e.begin(), e.end(), [&](array<ll, 3> a, array<ll, 3> b){
            return a[2] < b[2];
        });
        vector<int> p(r - l + 2);
        for(int i = 1; i <= r - l + 1; i++) p[i] = i;
        function<int(int)> find = [&] (int x){
            if(p[x] != x) return p[x] = find(p[x]);
            return p[x];
        };
        ll ans = 0;
        for(auto [u, v, w] : e){
            int pa = find(u), pb = find(v);
            if(pa == pb) continue;
            p[pa] = pb;
            ans += w;
        }
        cout << ans << '\n';
    }
    else {
        int idx = 0;
        for(int i = l; i <= r; i++){
            if(vis[i] == i){
                idx = i; break;
            }
        }
        vector<array<ll, 3>> e;
        for (int i = l; i <= r; i++) {
            int num = i, lst = 0;
            vector<int> ob;
            while (num != 1) {
                if(lst != vis[num]) ob.push_back(vis[num]), lst = vis[num];
                num = num / vis[num];
            }
            ne_l = l - 1, ne_r = r + 1, sz = ob.size();
            down = l, up = i;
            cal_l(0, 1, ob);
            down = i, up = r;
            cal_r(0, 1, ob);
            if(ne_l >= l){
                e.push_back({ne_l - l + 1, i - l + 1, sz});
            }
            if(ne_r <= r){
                e.push_back({i - l + 1, ne_r - l + 1, sz});
            }
            if(i != idx) e.push_back({i - l + 1, idx - l + 1, sz + (i % idx != 0)});
        }
        sort(e.begin(), e.end(), [&](array<ll, 3> a, array<ll, 3> b){
            return a[2] < b[2];
        });
        vector<int> p(r - l + 2);
        for(int i = 1; i <= r - l + 1; i++) p[i] = i;
        function<int(int)> find = [&] (int x){
            if(p[x] != x) return p[x] = find(p[x]);
            return p[x];
        };
        ll ans = 0;
        for(auto [u, v, w] : e){
            int pa = find(u), pb = find(v);
            if(pa == pb) continue;
            p[pa] = pb;
            ans += w;
        }
        cout << ans << '\n';
    }
}

int main(){
    init(N);
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t = 1;
    cin >> t;
    while(t--){
        solve();
    }
    return 0 - 0;
}