#include <cstdio>
#include <algorithm>
#include <vector>

#define X first
#define Y second
#define PB push_back

using namespace std;

typedef long long ll;

const int N = 1e6 + 500;

int par[N];

int pr(int x) {
	if(x == par[x]) return x;
	return par[x] = pr(par[x]);
}

void mrg(int x, int y) {
	par[pr(x)] = pr(y);
}

int w[N], t[N];
vector < int > dv[N];

void precompute(){
	for(int i = 1;i < N;i++) t[i] = 1, dv[i].PB(1);
	for(int i = 2;i < N;i++) {
		if(w[i] == 0) {
			for(int j = i;j < N;j += i) w[j]++, t[j] *= i;
		}
		if(t[i] == i) {
			for(int j = i;j < N;j += i) {
				if(t[j] == j) dv[j].PB(i);
			}
		}
	}
}

int l, r;
vector < int > p, d;
int naj[N], dr[N], un[N], cookie;
int grp[N], veza[N], kol[N];

ll boruvka_iter() {
	for(int x : p) grp[x] = pr(x), veza[grp[x]] = -1;
	for(int y : d) naj[y] = -1, dr[y] = -1;
	for(int x : p) {
		for(int y : dv[x]) {
			if(un[y] != cookie) break;
			if(naj[y] != -1 && grp[naj[y]] == grp[x] && w[x / y] < w[naj[y] / y]){
				naj[y] = x;
			} else if(naj[y] == -1 || (grp[naj[y]] != grp[x] && w[x / y] < w[naj[y] / y])) {
				dr[y] = naj[y]; naj[y] = x;
			} else if(dr[y] == -1 || w[x / y] < w[dr[y] / y]) {
				dr[y] = x;
			}
		}
	}
	for(int x : p) {
		for(int y : dv[x]) {
			if(un[y] != cookie) break;
			int cst = -1, tko = -1;
			if(grp[naj[y]] != grp[x])
				cst = w[x / y] + w[naj[y] / y] + w[y], tko = naj[y];
			else if(dr[y] != -1)
				cst = w[x / y] + w[dr[y] / y] + w[y], tko = dr[y];
			if(cst != -1 && (veza[grp[x]] == -1 || cst < kol[grp[x]])) {
				kol[grp[x]] = cst; veza[grp[x]] = grp[tko]; 
			}
		}
	}
	ll ret = 0;
	for(int x : p) {
		if(par[x] != x) continue;
		if(pr(x) != pr(veza[x])) {
			mrg(x, veza[x]);
			ret += kol[x];
		}
	}
	return ret;
}


void solve(){
	p.clear(); d.clear();
	scanf("%d%d", &l, &r);
	cookie++;
	for(int i = 1;i <= r - l;i++)
		if(t[i] == i) un[i] = cookie, d.PB(i);
	for(int i = l;i <= r;i++) {
		p.PB(t[i]);
	}
	sort(p.begin(), p.end());
	ll dod = 0;
	for(int i = 1;i < (int)p.size();i++)
		if(p[i] == p[i - 1]) dod += w[p[i]];
	p.erase(unique(p.begin(), p.end()), p.end());
	for(int x : p) par[x] = x;
	ll ans = 0;
	for(;;) {
		int poc = p[0], sve = 1;
		for(int x : p) {
			sve &= pr(x) == pr(poc);
		}
		if(sve) break;
		ans += boruvka_iter();
	}
	printf("%lld\n", ans + dod);
}

int main(){
	precompute();
	int T; scanf("%d", &T);
	for(;T--;) solve();
	return 0;
}