// what is matter? never mind. 
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
//#pragma GCC target("sse,sse2,sse3,sse4,popcnt,abm,mmx,avx,avx2") 
#include<bits/stdc++.h>
#define For(i,a,b) for(int i=(a);i<=(b);++i)
#define Rep(i,a,b) for(int i=(a);i>=(b);--i)
#define ll long long
#define ull unsigned long long
//#define int long long
using namespace std;
inline int read()
{
    char c=getchar();int x=0;bool f=0;
    for(;!isdigit(c);c=getchar())f^=!(c^45);
    for(;isdigit(c);c=getchar())x=(x<<1)+(x<<3)+(c^48);
    if(f)x=-x;return x;
}

#define fi first
#define se second
#define pb push_back
#define mkp make_pair
typedef pair<int,int>pii;
typedef vector<int>vi;
 
#define maxn 2000005
#define inf 0x3f3f3f3f

int mn[maxn],cnt[maxn],id[maxn];
bool vis[maxn];
int pri[maxn],tot;

void sieve(int n){
	mn[1]=1;
	For(i,2,n){
		if(!vis[i]) vis[i]=1,cnt[i]=1,mn[i]=i,id[i]=i,pri[++tot]=i;
		For(j,1,tot){
			int x=i*pri[j];
			if(x>n)break;
			vis[x]=1;
			mn[x]=pri[j];
			if(mn[i]==mn[x]) cnt[x]=cnt[i],id[x]=id[i];
			else cnt[x]=cnt[i]+1,id[x]=id[i]*pri[j];
			if(i%pri[j]==0)break;
		}
	}
}

int l,r;
int fa[maxn];
inline int getf(int x){
	while(x^fa[x])x=fa[x]=fa[fa[x]];
	return x;
} 

struct edge{
	int u,v,w;
	bool operator <(const edge&b)const{return w<b.w;}
}e[10000005];
int etot;

bool use[maxn];

void work()
{
	l=read(),r=read();
	For(i,l,r)fa[i]=i;
	For(i,1,r) use[id[i]]=0;
	For(i,1,r)
		if(!use[id[i]]){
			use[id[i]]=1;
			int tu=0,tw=inf;
			for(int j=i;j<=r;j+=i)
				if(j>=l) {
					if(cnt[j]<tw) tw=cnt[j],tu=j;
				}
			if(tw==inf) continue;
			for(int j=i;j<=r;j+=i)
				if(j>=l && j!=tu)
				//	cout<<"add "<<j<<" "<<tu<<" "<<cnt[j]+cnt[tu]-cnt[i]<<"\n",
					e[++etot]={j,tu,cnt[j]+cnt[tu]-cnt[i]};
		}
	int res=0;
	sort(e+1,e+etot+1);
	For(i,1,etot){
		int u=e[i].u,v=e[i].v;
		if(getf(u)!=getf(v))
			fa[getf(u)]=getf(v),res+=e[i].w; 
	}
	cout<<res<<"\n";
}

signed main()
{
	sieve(1000000);
	int T=read();
	while(T--)work();
	return 0;
}
/*

*/