// 長い夜の終わりを信じながら
// Think twice, code once.
#include <queue>
#include <vector>
#include <cstdio>
#include <string>
#include <cstring>
#include <iostream>
#include <algorithm>
#define eputchar(c) putc(c, stderr)
#define eprintf(...) fprintf(stderr, __VA_ARGS__)
#define eputs(str) fputs(str, stderr), putc('\n', stderr)
using namespace std;

int T, l, r, f[1000005], w[1000005], mul[1000005];
struct dsu {
	int fa[1000005];

	void clear(int l, int r) {for (int i = l; i <= r; i++) fa[i] = i; return;}
	int find(int x) {return x == fa[x] ? x : fa[x] = find(fa[x]);}
	void merge(int x, int y) {fa[find(x)] = find(y); return;}
	int query(int x, int y) {return find(x) == find(y);}
} d;
struct edge {
	int u, v, w;

	edge() = default;
	edge(int _u, int _v, int _w): u(_u), v(_v), w(_w) {}
};

int main() {
	for (int i = 1; i <= 1000000; i++) mul[i] = 1;
	for (int i = 2; i <= 1000000; i++)
		if (!w[i])
			for (int j = i; j <= 1000000; j += i) w[j]++, mul[j] *= i;
	scanf("%d", &T);
	while (T--) {
		scanf("%d%d", &l, &r);
		int flag = 0;
		for (int i = l; i <= r; i++) flag |= w[i] == 1, f[i] = 0;
		int ans = 0;
		if (l == 1) {
			for (int i = l; i <= r; i++) ans += w[i];
			printf("%d\n", ans);
		} else if (flag) {
			for (int i = l; i <= r; i++) ans += w[i], f[mul[i]] = 1;
			for (int i = 1; i <= r; i++)
				if (f[i]) {
					ans++;
					for (int j = i; j <= r; j += i) f[j] = 0;
				}
			printf("%d\n", ans - 2);
		} else {
			vector<edge> vec;
			for (int i = l; i <= r; i++)
				for (int j = l; j < i; j++)
					vec.emplace_back(i, j, w[i] + w[j] - w[__gcd(i, j)]);
			sort(vec.begin(), vec.end(), [](const edge &x, const edge &y) {return x.w < y.w;});
			d.clear(l, r);
			for (edge i : vec)
				if (!d.query(i.u, i.v)) ans += i.w, d.merge(i.u, i.v);
			printf("%d\n", ans);
		}
	}
	return 0;
}