#include <bits/stdc++.h>
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
#define st first
#define nd second
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const int N = 1e6 + 5;
int lp[N], pr[N], cnt = 0, sm[N];
vector<int> divi[N];

void solve() {
	int l, r; cin >> l >> r;
	ll ans = 0;
	vector<vector<pair<int, int>>> arr(r + 1);
	for (int i = l; i <= r; i++)
		for (int g: divi[i])
			arr[g].push_back({sm[i], i});
	for (int i = 1; i <= r; i++)
		sort(all(arr[i]));
	vector<int> par(r + 1);
	iota(all(par), 0);
	function<int(int)> qry = [&](int x) {
		return x == par[x] ? x : par[x] = qry(par[x]);
	};
	vector<int> ptr(r + 1);
	vector<vector<int>> comp(r + 1);
	for (int i = l; i <= r; i++)
		comp[i].push_back(i);
	int cnt = r - l + 1;
	while (cnt > 1) {
		vector<pair<int, int>> edg;
		for (auto& c: comp) {
			int opt = mod;
			pair<int, int> cand;
			for (int x: c) {
				for (int g: divi[x]) {
					while (ptr[g] < sz(arr[g])) {
						if (qry(arr[g][ptr[g]].nd) == qry(x)) {
							ptr[g]++;
							continue;
						}
						int val = sm[x] - sm[g] + arr[g][ptr[g]].st;
						if (val < opt) {
							opt = val;
							cand = {x, arr[g][ptr[g]].nd};
						}
						break;
					}
				}
			}
			for (int x: c)
				for (int g: divi[x])
					ptr[g] = 0;
			if (opt != mod)
				edg.push_back(cand);
		}
		for (auto [u, v]: edg) {
			if (qry(u) != qry(v))
				ans += sm[u] + sm[v] - sm[gcd(u, v)];
			u = qry(u);
			v = qry(v);
			if (u != v) {
				if (sz(comp[u]) > sz(comp[v]))
					swap(u, v);
				comp[v].insert(comp[v].end(), comp[u].begin(), comp[u].end());
				comp[u].clear();
				cnt--;
				par[u] = v;
			}
		}
	}
	cout << ans << "\n";
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(0);
	for (int i = 2; i < N; i++) {
		if (!lp[i])
			pr[cnt++] = lp[i] = i, sm[i] = 1;
		for (int j = 0; j < cnt && pr[j] * i < N && pr[j] <= lp[i]; j++) {
			sm[pr[j] * i] = sm[i] + (pr[j] != lp[i]);
			lp[pr[j] * i] = pr[j];
		}
	}
	for (int i = 1; i < N; i++) {
		for (int j = i; j < N; j += i)
			divi[j].push_back(i);
	}
	int t; cin >> t; while (t--) solve();
}