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

typedef long long ll;
typedef pair<int, int> pii;
#define F first
#define S second
#define All(x) (x).begin(), (x).end()
#define len(x) (int) (x).size()
#define pb push_back

const int N = 1e6 + 7;
int n, par[N], w[N];
bool mark[N];

int get_par(int u) {
	return par[u] < 0? u: par[u] = get_par(par[u]);
}

bool merge(int u, int v) {
	u = get_par(u), v = get_par(v);
	if (u == v)
		return false;
	if (par[u] < par[v])
		swap(u, v);
	par[v] += par[u];
	par[u] = v;
	return true;
}

int32_t main() {
	ios:: sync_with_stdio(0), cin.tie(0), cout.tie(0);
	for (int i = 2; i < N; i++) 
		if (!mark[i]) 
			for (int j = i; j < N; j += i) 
				mark[j] = true, w[j]++;
	int q;
	cin >> q;
	memset(par, -1, sizeof par);
	while (q--) {
		int l, r;
		cin >> l >> r;
		vector<pair<int, pii>> ed;
		for (int i = 1; i <= r; i++) {
			int who, mn;
			mn = INT_MAX;
			for (int j = i; j <= r; j += i)
				if (j >= l && w[j] <= mn) 
					who = j, mn = w[j];
			for (int j = i; j <= r; j += i)
				if (j >= l)
					ed.pb({w[who] + w[j] - w[gcd(who, j)], {j, who}});
		}
		int ans = 0;
		sort(All(ed));
		for (auto e: ed) 
			if (merge(e.S.F, e.S.S))
				ans += e.F;
		for (int i = l; i <= r; i++)
			par[i] = -1;
		cout << ans << '\n';
	}
	return 0;
}