#include<bits/stdc++.h>
using namespace std;
const int N=1e6+5;
vector<pair<int,int> >vec[30];
int T,l,r,pri[N],tot,mn[N],w[N],fa[N],ans,trans[N],rec[N];
bool vis[N];
inline int find(int x){while(x!=fa[x])x=fa[x]=fa[fa[x]];return x;}
vector<int>fac[N];
void sieve(int n){
	for(int i=2;i<=n;++i){
		if(!vis[i])pri[++tot]=i,mn[i]=i;
		for(int j=1;j<=tot&&i*pri[j]<=n;++j){
			vis[i*pri[j]]=1;
			mn[i*pri[j]]=min(mn[i],pri[j]);
			if(i%pri[j]==0)break;
		}
	}
	w[1]=0;
	for(int i=2;i<=n;++i)
		if(i/mn[i]%mn[i]==0)w[i]=w[i/mn[i]];
		else w[i]=w[i/mn[i]]+1;
	trans[1]=1;
	for(int i=2;i<=n;++i){
		int res=1,x=i;
		while(x>1){
			int t=mn[x];
			res*=t;
			while(x%t==0)x/=t;
		}
		trans[i]=res;
	}
	for(int i=2;i<=n;++i)if(trans[i]==i)
		for(int j=i+i;j<=n;j+=i)if(trans[j]==j)
			fac[j].emplace_back(i);
}
inline int getw(int x,int y){
	int res=0;
	x=trans[x],y=trans[y];
	while(x>1&&y>1){
		++res;
		if(mn[x]==mn[y])x/=mn[x],y/=mn[y];
		else if(mn[x]<mn[y])x/=mn[x];else y/=mn[y];
	}
	return res+w[x]+w[y];
}
int main(){
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	sieve(1000000);
	for(cin>>T;T--;){
		cin>>l>>r;
		ans=0;
		for(int i=0;i<30;++i)vec[i].clear();
		for(int i=l;i<=r;++i){
			fa[i]=i;
			if(!rec[trans[i]])rec[trans[i]]=i;
		}
		int t=l;
		for(int i=l+1;i<=r;++i)if(w[i]<w[t])t=i;
		for(int i=l;i<=r;++i){
			for(int j=i+1;j<=r&&j-i<=30;++j)vec[getw(i,j)].emplace_back(i,j);
//			continue;
			if(i!=t)vec[getw(i,t)].emplace_back(i,t);
			if(rec[trans[i]]&&rec[trans[i]]!=i)vec[w[i]].emplace_back(i,rec[trans[i]]);
			for(int x:fac[trans[i]])
				if(rec[x])vec[w[i]].emplace_back(i,rec[x]);
		}
		int e=0;
		for(int v=0;v<30;++v)
			for(auto it:vec[v]){
				int x=find(it.first),y=find(it.second);
				if(x!=y)++e,fa[y]=x,ans+=v;//,cerr<<it.first<<' '<<it.second<<endl;
			}
		assert(e==r-l);
		cout<<ans<<'\n';
		for(int i=l;i<=r;++i)rec[trans[i]]=0;
	}
	return 0;
}