#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;
}
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;
}
void ins(int x,int t,int T) {
	if(t>cnt || x>N/f[t]) return;
	val[x]=T;
	if(x%f[t]==0) ins(x,t+1,T);
	else {
		ins(x,t+1,T);
		ins(x*f[t],t+1,T);
	}
}
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++) {
		int nw=1,nx=i,lst=0;
		while(nx>1) {
			if(v[nx]!=lst) nw*=v[nx],lst=v[nx];
			nx/=v[nx];
		}
		pre[i]=val[nw];
		ins(nw,1,i);
	}
	memset(val,0xcf,sizeof(val));
	for(int i=N-1;i>=2;i--) {
		int nw=1,nx=i,lst=0;
		while(nx>1) {
			if(v[nx]!=lst) nw*=v[nx],lst=v[nx];
			nx/=v[nx];
		}
		nxt[i]=-val[nw];
		ins(nw,1,-i);
	}
//	for(int i=1;i<=10;i++) cout<<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(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() {
//	freopen("inn.in","r",stdin);
	init(); 
//	cout<<"!#@";
	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
*/