#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];

void solve() {
	int l, r; cin >> l >> r;
	ll ans = 0;
	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<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>> cand(r + 1, make_pair(mod, -1));
		auto upd = [&](int x, int y) {
			int val = sm[x] + sm[y] - sm[gcd(x, y)];
			cand[qry(x)] = min(cand[qry(x)], make_pair(val, y));
		};
		for (int g = r; g >= 1; g--) {
			vector<pair<int, int>> arr;
			for (int x = g; x <= r; x += g) {
				if (x >= l)
					arr.push_back({sm[x], x});
			}
			sort(all(arr));
			int j = 0;
			while (j < sz(arr) && qry(arr[j].nd) == qry(arr[0].nd))
				j++;
			if (j == sz(arr))
				continue;
			for (auto [s, x]: arr) {
				if (qry(x) == qry(arr[0].nd))
					upd(x, arr[j].nd);
				else
					upd(x, arr[0].nd);
			}
		}
		for (int i = l; i <= r; i++) {
			if (i != qry(i)) continue;
			int u = i, v = cand[i].nd;
			if (v == -1)
				continue;
			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];
		}
	}
	int t; cin >> t; while (t--) solve();
}