#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
int f[N],v[N],cnt;
int pre[N],nxt[N],w[N];
int len,sum[N],fa[N];
vector<int> dc,cl;
int gts(int x) {
	if(fa[x]!=x) fa[x]=gts(fa[x]);
	return fa[x];
}

int ck(int x) {
	int lst=0,ans=0;
	int nw=x;
	while(nw>1) {
		if(v[nw]!=lst) ans++;
		lst=v[nw]; nw/=v[nw];
	}
	return ans;
}

void dfs(int t,long long x) {
	if(t==len) {cl.push_back(x);return;}
	while(x<N) {
		dfs(t+1,x);
		x*=dc[t];
	}
}

void slv(int x) {
	dc.clear(); cl.clear(); len=0;
	int lst=0;
	int nw=x;
	while(nw>1) {
		if(v[nw]!=lst) dc.push_back(v[nw]),len++;
		lst=v[nw]; nw/=v[nw];
	}
	dfs(0,1);
}

void init() {
	for(int i=2;i<N;i++) {
		if(!v[i]) {v[i]=i;f[++cnt]=i;}
		for(int j=1;j<=cnt;j++) {
			if(f[j]>v[i] || f[j]>N/i) break;
			v[f[j]*i]=f[j];
		}
	}
	for(int i=1;i<N;i++) {
		fa[i]=i; w[i]=ck(i);
		sum[i]=sum[i-1]+w[i];
	}
	for(int i=2;i<N;i++) {
		if(pre[i] || nxt[i]) continue;
		slv(i);
		sort(cl.begin(),cl.end());
		int ln=cl.size();
		for(int j=0;j<ln;j++) {
			if(w[cl[j]]!=len) continue;
			if(j) pre[cl[j]]=cl[j-1];
			if(j<ln-1) nxt[cl[j]]=cl[j+1];
		}
	}
}

struct sd {
	int x,y,w;
	bool operator < (const sd & T) const {
		return w<T.w;
	}
} e[3*N];
inline int gcd(int x,int y) {
	return y?gcd(y,x%y):x;
}
inline int lcm(int x,int y) {
	return w[x]+w[y]-w[gcd(x,y)];
}
int solve(int l,int r) {
	if(l==1) return sum[r];
	int tot=0;
	if(r-l+1<=114) {
		for(int i=l;i<=r;i++)
			for(int j=i+1;j<=r;j++)
				e[++tot]=sd{i,j,lcm(i,j)};
	} else {
		int pm=0;
		for(int i=l;i<=r;i++) if(v[i]==i) {pm=i; break;}
		for(int i=l;i<=r;i++) {
			if(pre[i] && pre[i]>=l) e[++tot]=sd{pre[i],i,w[i]};
			if(nxt[i] && nxt[i]<=r) e[++tot]=sd{nxt[i],i,w[i]};
			e[++tot]=sd{i,pm,w[i]+1};
		}
	}
	sort(e+1,e+tot+1);
	int ans=0;
	for(int i=1;i<=tot;i++) {
		int x=gts(e[i].x),y=gts(e[i].y);
		if(x!=y) {
	//		cout<<e[i].w<<"\n";
			ans+=e[i].w;
			fa[x]=y;
		}
	}
	for(int i=l;i<=r;i++) fa[i]=i;
	return ans;
}

int main() {
	init(); 
	int T;scanf("%d",&T);
	
	while(T--) {
		int l,r;scanf("%d%d",&l,&r);
//		cout<<"-------------------------------------";
		cout<<solve(l,r)<<"\n";
	}
	return 0;
}
/*
1
19 810
*/