#include <bits/stdc++.h>

using namespace std;
using ll = long long;
const int MAXN=1e6+7;
const ll mod=1e9+7LL;
int n,m;
int cnt=0,prime[MAXN];
bool vis[MAXN];
vector<int> p[MAXN];
int num[MAXN],sum[MAXN],s[MAXN];
int fa[MAXN],c[MAXN];
struct hhh
{
	int to,nxt;
	int w;
}a[MAXN*3];
inline bool cmp(hhh x,hhh y)
{
	return x.w<y.w;
}
int find_fa(int x)
{
	if(fa[x]==x) return x;
	fa[x]=find_fa(fa[x]);
	return fa[x];
}
void pre()
{
	vis[1]=1;num[1]=0;
	int lim=1e6;
	for(int i=2;i<=lim;i++)
	{
		if(!vis[i]) prime[++cnt]=i;
		for(int j=1;j<=cnt && i*prime[j]<=lim;j++)
		{
			vis[i*prime[j]]=1;
			if(i%prime[j]==0) break;
		}
	}
	sum[1]=0;
	for(int i=2;i<=lim;i++)
	{
		p[i].push_back(0);
		int x=i;s[i]=1LL;
		for(int j=1;j<=cnt && prime[j]<=x;j++)
		{
			if(prime[j]>sqrt(x)+2) break;
			if(x%prime[j]==0)
			{
				num[i]++;s[i]*=prime[j];
				p[i].push_back(prime[j]);
				while(x%prime[j]==0) x/=prime[j];
			}
		}
		if(x!=1) num[i]++,p[i].push_back(x),s[i]*=x;
		sum[i]=sum[i-1]+num[i];
	}
	return;
}
int d[MAXN],tot=0;
int work(int x,int y)
{
	int res=num[x];
	for(int i=1;i<=num[y];i++)
	{
		bool kkk=1;
		for(int j=1;j<=num[x];j++)
		{
			if(p[y][i]==p[x][j])
			{
				kkk=0;
				break;
			}
		}
		if(kkk) res++;
	}
	return res;
}
int l,r,minl[MAXN];
int id[MAXN];
map<int,int> ton,pd;
int main() {
	cin.tie(nullptr) -> sync_with_stdio(false);
	
	pre();
//	for(int i=1;i<=1000000;i++)
//	{
//		if(!vis[i])
//		{
//			bool flag=1;
//			for(int j=i+1;j<=i*2;j++)
//			{
//				if(j>1000000) break;
//				if(!vis[j])
//				{
//					flag=0;
//					break;
//				}
//			}
//			if(flag) cout<<i<<" ad"<<endl;
//		}
//	}
	int t;
	cin>>t;
	while(t--)
	{
		cin>>l>>r;
		if(l==1)
		{
			cout<<sum[r]-sum[l-1]<<'\n';
			continue;
		}
		bool kkk=0;
		for(int i=l;i<=r;i++)
		{
			fa[i]=i;
			if(!vis[i]) kkk=1;
		}
		if(l>=999983) kkk=0;
//		kkk=0;
		ll ans=0LL;
		tot=0;
		if(kkk)
		{
			pd.clear();
			n=0;
			for(int i=l;i<=r;i++) c[++n]=s[i];
			sort(c+1,c+1+n);
			int numk=0;
			for(int i=1;i<=n;i++)
			{
				int numg=0;
				d[++numk]=c[i];
				while(i<n&&c[i]==c[i+1]) i++,numg++;
				ans+=numg*num[c[i]];
			}
			n=numk;
			for(int i=1;i<=n;i++) c[i]=d[i],pd[c[i]]=1,fa[c[i]]=c[i],minl[c[i]]=1e9;
//			for(int i=1;i<=n;i++) cerr<<c[i]<<"  ad"<<endl;
//			cerr<<ans<<" asd"<<endl;
			ton.clear();
			for(int i=1;i<=n;i++)
			{
				if(ton[c[i]]) continue;
				ton[c[i]]=1;
				for(int j=2;;j++)
				{
					int sss=c[i]*j;
					if(sss>c[n]) break;
					if(ton[sss]) continue;
					if(pd[sss])
					{
						ton[sss]=1;
						ans+=num[sss];
						fa[sss]=c[i];
//						cerr<<sss<<" "<<c[i]<<"  asd"<<endl;
//						pre=sss;
					}
				}
			}
//			cerr<<ans<<" asd"<<endl;
			for(int i=1;i<=n;i++)
			{
				if(fa[c[i]]==c[i]) ans+=num[c[i]]+1;
			}
			ans-=2;
		}
		else
		{
			
			for(int i=l;i<=r;i++)
			{
				for(int j=i+1;j<=r;j++)
				{
					if(i==j) continue;
					a[++tot].to=i;
					a[tot].nxt=j;
					a[tot].w=work(i,j);
				}
			}
			sort(a+1,a+1+tot,cmp);
			int cnt=0;
			for(int i=1;i<=tot;i++)
			{
				int fa1=find_fa(a[i].to);
				int fa2=find_fa(a[i].nxt);
				if(fa1==fa2) continue;
				cnt++;ans+=a[i].w;
				fa[fa2]=fa1;
				if(cnt==r-l) break;
			}
		}
		cout<<ans<<'\n';
	}
	return 0;
}
/*
1
5
2 1 3 2 1
5 1 1 3 4
1 3 4 2 4


4
4
2 5 5 2
4 2 1 3
3 2 1 4
3
5 4 3
1 1 1
6 6 6
3
5 4 3
2 3 1
1 2 3
5
2 1 3 2 1
5 1 1 3 4
1 3 4 2 4
*/