#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

struct DSU {
    static const int N = 1e6 + 10;
    int Parent[N], Rank[N], Size[N], cnt;
    void init(int n) {
        for (int i = 1; i <= n; i++) {
            Parent[i] = i, Rank[i] = 0, Size[i] = 1;
        }
        cnt = n;
    }
    int find(int v) {
        if (Parent[v] == v) return v;
        else return Parent[v] = find(Parent[v]);
    }
    void unite(int u, int v) {
        u = find(u), v = find(v);
        if (u == v) return;
        if (Rank[u] < Rank[v]) swap(u, v);
        if (Rank[v] == Rank[u]) Rank[u]++;
        Parent[v] = u, cnt--;
        Size[u] += Size[v];
    }
};

DSU dsu;

const int MAX_DIV = 7;
const int C = 1e6 + 10;
bool prime[C];
int prime_div[C];
vector<int> pf[C];
int mem_sz[C][MAX_DIV + 1];
vector<int> vec[C][MAX_DIV + 1];

void find_primes() {
    for (int i = 0; i <= C - 1; i++) {
        prime[i] = true;
        prime_div[i] = i;
    }
    prime[0] = prime[1] = false;
    for (int i = 2; i <= C - 1; i++) {
        if (prime[i]) {
            if (i * 1ll * i <= C - 1) {
                for (int j = i * i; j <= C - 1; j += i) {
                    prime[j] = false;
                    prime_div[j] = i;
                }
            }
        }
    }
    for (int i = 2; i <= C - 1; i++) {
        // pf[i].reserve(MAX_DIV);
        if (prime[i]) {
            pf[i] = {i};
        } else {
            pf[i] = pf[i / prime_div[i]];
            bool ok = true;
            for (int j = 0; j < pf[i].size(); j++) {
                if (pf[i][j] == prime_div[i]) {
                    ok = false;
                }
            }
            if (ok) {
                pf[i].push_back(prime_div[i]);
                for (int j = int(pf[i].size()) - 1; j >= 1; j--) {
                    if (pf[i][j - 1] > pf[i][j]) {
                        swap(pf[i][j - 1], pf[i][j]);
                    }
                }
            }
        }
    }
    int tot = 0;
    for (int i = 1; i <= C - 1; i++) {
        int red = 1;
        for (int p : pf[i]) {
            red *= p;
        }
        int k = pf[red].size();
        tot += (1 << k);
        for (int mask = 0; mask < (1 << k); mask++) {
            int g = 1;
            for (int i = 0; i < k; i++) {
                if (mask & (1 << i)) {
                    g *= pf[red][i];
                }
            }
            int l = k - __builtin_popcount(mask);
            mem_sz[g][l]++;
            // vec[g][l].push_back(i);
        }
    }
    for (int g = 1; g <= C - 1; g++) {
        for (int l = 0; l <= MAX_DIV; l++) {
            vec[g][l].reserve(mem_sz[g][l]);
        }
    }
    for (int i = 1; i <= C - 1; i++) {
        int red = 1;
        for (int p : pf[i]) {
            red *= p;
        }
        int k = pf[red].size();
        for (int mask = 0; mask < (1 << k); mask++) {
            int g = 1;
            for (int i = 0; i < k; i++) {
                if (mask & (1 << i)) {
                    g *= pf[red][i];
                }
            }
            int l = k - __builtin_popcount(mask);
            vec[g][l].push_back(i);
        }
    }
}

int solve(int l, int r) {
    int ans = 0;
    dsu.init(r);

    for (int cost = 1; cost <= 2 * MAX_DIV - 1; cost++) {
        for (int g = 1; g <= r; g++) {
            if (pf[g].size() > cost) {
                continue;
            }
            if (!((cost - pf[g].size()) & 1)) {
                int x_cnt = (cost - pf[g].size()) / 2;
                if (x_cnt <= MAX_DIV) {
                    for (int i = 0; i + 1 < vec[g][x_cnt].size() && vec[g][x_cnt][i + 1] <= r; i++) {
                        if (l <= vec[g][x_cnt][i] && dsu.find(vec[g][x_cnt][i]) != dsu.find(vec[g][x_cnt][i + 1])) {
                            dsu.unite(vec[g][x_cnt][i], vec[g][x_cnt][i + 1]);
                            ans += cost;
                        }
                    }
                }
            }
            for (int x_cnt = 0; x_cnt + x_cnt < cost - pf[g].size(); x_cnt++) {
                if (x_cnt > MAX_DIV) {
                    continue;
                }
                int y_cnt = cost - pf[g].size() - x_cnt;
                if (y_cnt > MAX_DIV) {
                    continue;
                }
                int mem_x = 0;
                for (int x : vec[g][x_cnt]) {
                    if (x > r) {
                        break;
                    } else if (l <= x) {
                        mem_x = x;
                        break;
                    }
                }
                if (!mem_x) {
                    continue;
                }
                for (int y : vec[g][y_cnt]) {
                    if (y > r) {
                        break;
                    } else if (l <= y) {
                        if (dsu.find(mem_x) != dsu.find(y)) {
                            dsu.unite(mem_x, y);
                            ans += cost;
                        }
                    }
                }
            }
        }
    }
    return ans;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
#ifdef LOCAL
    freopen("input.txt", "r", stdin);
#endif

    find_primes();

    int t;
    cin >> t;
    while (t--) {
        int l, r;
        cin >> l >> r;
        cout << solve(l, r) << "\n";
    }

#ifdef LOCAL
    cout << "\nTime elapsed: " << double(clock()) / CLOCKS_PER_SEC << " s.\n";
#endif
}