#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;
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 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;
	}
	++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;
	rep(L,R,i)
	{
		f[w[i]]=w[i];
		del(i);
	}
	
	l=0;
	
	rep(L,R,i)
	{
		if(c[w[i]])
		{
			ans+=h[i];
			continue;
		}
		
		add(i);
		flag=0;tr=w[i];
		dfs(1,1);	
		
		if(flag)
		{
			c[w[i]]=1;
			ans+=h[i];	
		}
		else
		{
			s[++l]=w[i];
		}
		del(i);
	}
	
	
	rep(1,l,i)
	{
		int x=s[i];
		f[x]=x;
		add(x);
		rep(i+1,l,j)
		{
			int y=s[j];
			add(y);
			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);
		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()
{
	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;	
		} 
		if(L==1)
		{
			int ans=0;
			rep(2,R,i)
			{
				add(i);
				ans+=cnt;
				del(i);
			}
			put(ans);
			continue;
		}
		mx=0;
		rep(1,top,j)
		{
			if(p[j]<=R)mx=p[j];
		}
		
		rep(L,R,i)
		{
			add(i);
			w[i]=kk;
			h[i]=cnt;
		}
		
		if(mx<L)
		solve1();
		else solve2();
		rep(L,R,i)
		{
			c[w[i]]=0;
			vis[w[i]]=0;
		}
		
	}q
	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
*/

answer.code: In function ‘int main()’:
answer.code:223:11: error: expected ‘;’ before ‘return’
  223 |         }q
      |           ^
      |           ;
  224 |         return 0;
      |         ~~~~~~
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:173:9: note: in expansion of macro ‘sc’
  173 |         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:183:17: note: in expansion of macro ‘sc’
  183 |                 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:183:23: note: in expansion of macro ‘sc’
  183 |                 sc(L);sc(R);
      |                       ^~