#include<bits/stdc++.h>
#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;
struct wy
{
	int x,y,v;
}t[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 g[MAXN];
int vis[MAXN];
int cmp(wy a,wy b){return a.v<b.v;
}
void solve1()
{
	int cc=0;
	rep(L,R,i)f[i]=i;
	rep(L,R,i)
	{
		int x=i,cnt=0;
		while(x!=1)
		{
			int ww=v[x];
			++g[ww];
			cnt+=g[ww]==1;
			x/=ww;
		}
		rep(i+1,R,j)
		{
			int y=j;
			while(y!=1)
			{
				int ww=v[y];
				++g[ww];
				cnt+=g[ww]==1;
				y/=ww;
			}
			t[++cc]=(wy){i,j,cnt};
			y=j;
			while(y!=1)
			{
				int ww=v[y];
				cnt-=g[ww]==1;
				--g[ww];
				y/=ww;
			}
			x=i;
			while(x!=1)
			{	
				int ww=v[x];
				cnt-=g[ww]==1;
				--g[ww];
				x/=ww;
			}
		}
	}
	sort(t+1,t+1+cc,cmp);
	int ans=0;
	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);
}
int flag=0;
int q[MAXN],r;
int w[MAXN],l; 
void dfs(int x,int dep)
{
	if(flag)return;
	if(dep==r+1)
	{
		if(vis[x])flag=1;
		return;
	}
	dfs(x*q[dep],dep+1);
	dfs(x,dep+1);
}
void solve2()
{
	int ans=0;
	l=0;
	rep(L,R,i)
	{
		if(i==mx)continue;
		int x=i,cnt=0,kk=1;
		r=0;
		while(x!=1)
		{
			int ww=v[x];
			++g[ww];
			if(g[ww]==1)
			{
				kk*=ww;
				q[++r]=ww;
				cnt+=g[ww]==1;
			}
			
			x/=ww;
		}
		flag=0;
		dfs(1,1);
		vis[kk]=1;
		w[++l]=kk;
		if(flag)ans+=cnt;
		else ans+=cnt+1;
		x=i;
		while(x!=1)
		{	
			int ww=v[x];
			cnt-=g[ww]==1;
			--g[ww];
			x/=ww;
		}
	}
	rep(1,l,i)
	{
		vis[w[i]]=0;
	}
	put(ans);
}
int main()
{
	sc(T);
	prepare();
	while(T--)
	{
		sc(L);sc(R);
		if(L==R)
		{
			put(0);
			continue;	
		} 
		if(L==1)
		{
			int ans=0;
			rep(2,R,i)
			{
				int x=i,cnt=0;
				while(x!=1)
				{
					int ww=v[x];
					++g[ww];
					cnt+=g[ww]==1;
					x/=ww;
				}
				ans+=cnt;
				x=i;
				while(x!=1)
				{	
					int ww=v[x];
					cnt-=g[ww]==1;
					--g[ww];
					x/=ww;
				}
			}
			put(ans);
			continue;
		}
		mx=0;
		rep(1,top,j)
		{
			if(p[j]<=R)mx=p[j];
		}
		//if(mx<L)
		solve1();
		//else solve2();
	}
	return 0; aaaaaaa
}

/*
5
1 1
4 5
1 4
1 9

1
19 810


2


27 30
183704 252609
*/

answer.code: In function ‘int main()’:
answer.code:199:19: error: ‘aaaaaaa’ was not declared in this scope
  199 |         return 0; aaaaaaa
      |                   ^~~~~~~
answer.code:3:20: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
    3 | #define sc(A) scanf("%d",&A)
      |               ~~~~~^~~~~~~~~
answer.code:154:9: note: in expansion of macro ‘sc’
  154 |         sc(T);
      |         ^~
answer.code:3:20: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
    3 | #define sc(A) scanf("%d",&A)
      |               ~~~~~^~~~~~~~~
answer.code:158:17: note: in expansion of macro ‘sc’
  158 |                 sc(L);sc(R);
      |                 ^~
answer.code:3:20: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
    3 | #define sc(A) scanf("%d",&A)
      |               ~~~~~^~~~~~~~~
answer.code:158:23: note: in expansion of macro ‘sc’
  158 |                 sc(L);sc(R);
      |                       ^~