//#include<bits/stdc++.h>
#include<iostream>
#include<cstdio>
#include<ctime>
#include<cctype>
#include<queue>
#include<deque>
#include<stack>
#include<iostream>
#include<iomanip>
#include<cstdio>
#include<cstring>
#include<string>
#include<ctime>
#include<cmath>
#include<cctype>
#include<cstdlib>
#include<queue>
#include<deque>
#include<stack>
#include<vector>
#include<algorithm>
#include<utility>
#include<bitset>
#include<set>
#include<map>
#define ll long long
#define sc(A) scanf("%d",&A)
#define rep(a,b,c) for(int c=a;c<=b;++c)
#define put(A) printf("%d\n",A)
using namespace std;
const int MAXN=1000010;
int T,n,top;
int maxx=1000000;
int v[MAXN],p[MAXN];
int f[MAXN];
int L,R,mx;
int g[MAXN],cnt,kk;
int vis[MAXN];
struct wy
{
	int x,y,v;
}t[MAXN];
int flag=0;
int q[MAXN],r,tr;
int s[MAXN],l;
int w[MAXN],h[MAXN],c[MAXN]; 
void prepare()
{
	rep(2,maxx,i)
	{
		if(!v[i])
		{
			v[i]=i;
			p[++top]=i;
		}
		rep(1,top,j)
		{
			if(p[j]>maxx/i)break;
			v[p[j]*i]=p[j];
			if(p[j]==v[i])break;
		}
	}
}
int getfather(int x){return f[x]==x?x:f[x]=getfather(f[x]);}

int cmp(wy a,wy b){return a.v<b.v;}
void add(int x,int y)
{
	int cc=x;kk=1;r=0;
	while(cc!=1)
	{
		int ww=v[cc];
		++g[ww];
		if(g[ww]==1)
		{
			cnt+=1;
			kk*=ww;
			q[++r]=ww;
		}
		cc/=ww;
	}
	if(y)++vis[kk];
}
void del(int x)
{
	int cc=x;
	while(cc!=1)
	{
		int ww=v[cc];
		if(g[ww]==1)
		{
			--cnt;
		}
		cc/=ww;
		--g[ww];
	}
}
void dfs(int x,int dep)
{
	if(flag)return;
	if(dep==r+1)
	{
		if(x==tr)return;
		if(vis[x])flag=1;
		return;
	}
	dfs(x*q[dep],dep+1);
	dfs(x,dep+1);
}
void solve1()
{
	int cc=0;
	int ans=0;
	l=0;
	//rep(1,R,i)c[i]=0;
	//rep(1,R,i)vis[i]=0;
	rep(L,R,i)
	{
		if(c[w[i]])
		{
			ans+=h[i];
			continue;
		}
		
		add(i,0);
		flag=0;tr=w[i];
		dfs(1,1);	
		
		if(flag)ans+=h[i];	
		else s[++l]=w[i];

		c[w[i]]=1;
		del(i);
	}
	
//	cout<<ans<<endl; 
	//rep(1,R,i)f[i]=i;
	rep(1,l,i)
	{
		int x=s[i];
		f[x]=x;
		add(x,0);
		rep(i+1,l,j)
		{
			int y=s[j];
			add(y,0);
			t[++cc]=(wy){x,y,cnt};
			del(y);
		}
		del(x);
	}
	sort(t+1,t+1+cc,cmp);
	rep(1,cc,i)
	{
		int xx=getfather(t[i].x);
		int yy=getfather(t[i].y);
		if(xx==yy)continue;
		f[xx]=yy;ans+=t[i].v; 
	}
	put(ans);
}


void solve2()
{
	int ans=0;
	rep(L,R,i)
	{
		if(c[w[i]])
		{
			ans+=h[i];
			continue;
		}
		if(i==mx)continue;
		add(i,0);
		flag=0;tr=w[i];
		dfs(1,1);
		//cout<<flag<<endl;
		if(flag)ans+=h[i];
		else ans+=h[i]+1; 
		c[w[i]]=1;
		del(i);
	} 
	put(ans);
}
int main()
{
	freopen("1.in","r",stdin);
	sc(T);
	prepare();
//	int cz=0;
//	rep(1,top,i)
//	{
//		cz=max(cz,p[i]-p[i-1]);
//	}
//	put(cz);
	while(T--)
	{
		sc(L);sc(R);
		if(L==R)
		{
			put(0);
			continue;	
		} 
		rep(L,R,i)
		{
			add(i,1);
			w[i]=kk;
			h[i]=cnt;
			del(i);
		}
		
		if(L==1)
		{
			int ans=0;
			rep(2,R,i)ans+=h[i];
			put(ans);
			rep(L,R,i)
			{
				c[w[i]]=0;
				vis[w[i]]=0;
			}
			continue;
		}
		mx=0;
		rep(1,top,j)
		{
			if(p[j]<=R)mx=p[j];
			else break;
		}
		
//		memset(f,0,sizeof(f));
//		memset(c,0,sizeof(c));
//		memset(vis,0,sizeof(vis));
		if(mx<L)
		solve1();
		else solve2();
		rep(L,R,i)
		{
			c[w[i]]=0;
			vis[w[i]]=0;
		}
//		rep(1,R,i)
//		{
//			if(c[i])cout<<"ww"<<endl;
//			if(vis[i])
//			{
//				cout<<i<<' '<<"ww"<<endl;
//				return 0;
//			}
//		}
	}
	return 0; 
}

/*
5
1 1
4 5
1 4
1 9
1
27 30
1
19 810


2

4
27 30
183704 252609
183704 252609
183704 252609
*/