#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<map>
#include<vector>
#include<queue>
#include<set>
#include<bitset>
#include<deque>
#include<stack>
#include<unordered_map>
#include<ctime>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
const int N=1e6+10;
struct node
{
	int x,y,v;
}e[N*10];
int vis[N],f[N];
vector<int>v[N];
int gcd(int x,int y){return y==0?x:gcd(y,x%y);}
int bcj(int x){return f[x]==x?x:f[x]=bcj(f[x]);}
bool cmp(node A,node B){return A.v<B.v;}
int main()
{
	for(int i=2;i<=1000000;i++)
		if(!vis[i])
		{
			v[i].push_back(i);
			for(int j=i*2;j<=1000000;j+=i)
				v[j].push_back(i),vis[j]=1;
		}
	int T;scanf("%d",&T);
	while(T--)
	{
		int L,R;scanf("%d%d",&L,&R);
		if(L==1)
		{
			int ans=0;
			for(int i=2;i<=R;i++) ans+=v[i].size();
			printf("%d\n",ans);
			continue;
		}
		int tt=0;
		for(int i=L;i<=R;i++)
			if(!vis[i]) tt=i;
		int ans=0;
		if(!tt)
		{
			for(int i=L;i<=R;i++) f[i]=i;int m=0;
			for(int i=L;i<=R;i++)
				for(int j=i+1;j<=R;j++)
					e[++m]=node{i,j,v[i].size()+v[j].size()-v[gcd(i,j)].size()};
			sort(e+1,e+m+1,cmp);
			for(int i=1,t=0;i<=m&&t<(R-L);i++)
			{
				int x=bcj(e[i].x),y=bcj(e[i].y);
				if(x==y) continue;
				f[x]=y;t++,ans+=e[i].v;
			}
		}
		else
		{
			for(int i=L;i<=R;i++) f[i]=i;int m=0;
			for(int i=L;i<=R;i++)
			{
				int p=1;
				for(int j=0;j<v[i].size();j++) p*=v[i][j];
				for(int j=(L+p-1)/p*p;j<=R;j+=p)
					if(i!=j) e[++m]=node{i,j,v[j].size()};
			}
			for(int i=L;i<=R;i++)
				if(i!=tt) e[++m]=node{i,tt,v[i].size()+1};
			sort(e+1,e+m+1,cmp);
			for(int i=1,t=0;i<=m&&t<(R-L);i++)
			{
				int x=bcj(e[i].x),y=bcj(e[i].y);
				if(x==y) continue;
				f[x]=y;t++,ans+=e[i].v;
			}
		}
		printf("%d\n",ans);
	}
	return 0;
}