#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 abc[N];
int len,sum[N],fa[N],fw[N];
int gts(int x) {
	if(fa[x]!=x) fa[x]=gts(fa[x]);
	return fa[x];
}

vector<int> dc[N];

int ck(int x) {
	int lst=0,ans=0;
	int nw=x;fw[x]=1;
	while(nw>1) {
		if(v[nw]!=lst) ans++,fw[x]*=v[nw];
		lst=v[nw]; nw/=v[nw];
	}
	return ans;
}
int val[N];
inline int Max(int x,int y) {
	return x>y?x:y;
}
inline int Min(int x,int y) {
	return x<y?x:y;
}
int TT; 
void ins(int x,int t) {
	dc[TT].push_back(x);
	if(t>cnt || x>N/f[t]) return;
	if(x%f[t]==0) ins(x,t+1);
	else {
		ins(x,t+1);
		ins(x*f[t],t);
	}
}
void init() {
	for(int i=2;i<N;i++) {
		if(!v[i]) {v[i]=i;f[++cnt]=i;abc[i]=1;}
		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++) {
		abc[i]+=abc[i-1];
		fa[i]=i; w[i]=ck(i);
		sum[i]=sum[i-1]+w[i];
	}
	for(int i=2;i<N;i++)
		if(i==fw[i]) TT=i,ins(i,1);
		
	for(int i=2;i<N;i++) {
		pre[i]=val[fw[i]];
		int len=dc[fw[i]].size();
		for(int j=0;j<len;j++) val[dc[fw[i]][j]]=i;
	}
	
	memset(val,0x3f,sizeof(val));
	for(int i=N-1;i>=2;i--) {
		nxt[i]=val[fw[i]];
		int len=dc[fw[i]].size();
		for(int j=0;j<len;j++) val[dc[fw[i]][j]]=i;
	}
	for(int i=1;i<N;i++) if(v[i]==i) pre[i]=1,nxt[i]=0;
//	for(int i=1000;i<=2000;i++) cout<<i<<" "<<pre[i]<<" "<<nxt[i]<<"\n";
}

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(abc[r]==abc[l-1]) {
		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() {
	freopen("inn.in","r",stdin);
	freopen("out.out","w",stdout);
	init(); 
	int T;scanf("%d",&T);
	
	while(T--) {
		int l,r;scanf("%d%d",&l,&r);
	//	solve(l,r);
		cout<<solve(l,r)<<"\n";
	}
	return 0;
}
/*
1
19 810
*/