#include<bits/stdc++.h>
using namespace std;
//#define int long long
const int N=1e6+10;
int st[N],primes[N],mp[N],zxzys[N],cnt,mul[N],pos[N],l[N],pos1[N],r[N],cntt[N],w[N],mpp[N],rd[N],d[10010][10010],ans,stt[N],dist[N],l1,r1;
void prim(int root){
    dist[root]=0;
    while(1){
        int pos=-1;
        int minn=1e9;
        for(int i=l1;i<=r1;i++){
            if(stt[i]==0){
                if(dist[i]<minn){
                    minn=dist[i];
                    pos=i;
                }
            }
        }
        if(pos==-1)return;
        stt[pos]=1;
        ans+=dist[pos];
        dist[pos]=0;
        //cnt++;
        for(int i=l1;i<=r1;i++){
            if(stt[i]==0){
                if(d[pos][i]<dist[i]){
                   dist[i]=d[pos][i]; 
                }
            }
        }
    }
}
int main(){
	//puts("fuck");
	
	for(int i=2;i<=1000000;i++){
		if(st[i]==0){
			mp[i]=1;
            cnt++;
            //cout<<i<<endl;
            primes[cnt]=i;
            for(int j=1;j*i<=1000000;j++){
            	//if(i*j==1339)cout<<i<<endl;
                st[j*i]=1;
                zxzys[j*i]=i;
            }
    }
	}
//cout<<mp[1339]<<endl;
//	puts("fuck");
//	s[1].insert(1);
	for(int i=2;i<=1000000;i++){
		int i1=i;
		set<int>s;
		while(i1!=1){
			s.insert(zxzys[i1]);
			int i2=i1;
			while(i2%zxzys[i1]==0){
				i2/=zxzys[i1];
			}
			i1=i2;
		}
		w[i]=s.size();
		int zt=1;
		for(auto j:s){
			zt*=j;
		}
		mul[i]=zt;
		//if(i>30)break;
	}
		//return 0;
	//cout<<w[30]<<endl;
	//puts("fuck");
//	for(int i=1;i<=1000000;i++){
//		int zt=1;
//		for(auto j:s[i]){
//			zt*=j;
//		}
//		mul[i]=zt;
//	}
//	puts("fuck");
//	return 0;
	for(int i=2;i<=N-10;i++){
		set<int>s;
		s.insert(1);
		//cout<<i<<" "<<s1[i].size()<<endl;
		int zt=mul[i];
//		cout<<i<<" "<<zt<<" "<<mul[i]<<endl;
//		cout<<i<<endl;
		while(zt!=1){
			int cnt1=0; 
			for(auto j:s){
				//int cnt1=0;
				cnt1++;
				cntt[cnt1]=j;
				
			}
			for(int j=1;j<=cnt1;j++){
				s.insert(cntt[j]*zxzys[zt]);
			}
			int ztt=zt;
			while(ztt%zxzys[zt]==0){
				ztt/=zxzys[zt];
			}
			zt=ztt;
			
		}
		//puts("fuck"); 
	//if(i==30)cout<<s1[i].size()<<endl; 
		for(auto j:s){
//			cout<<s1[i].size()<<endl;
//			cout<<j<<endl;
			if(pos[j])l[i]=max(l[i],pos[j]);
		}
//		if(i==30){
//			cout<<l[i]<<endl;
//			return 0;
//		}
		pos[mul[i]]=i;
	} 
//	puts("fuck");
	for(int i=N-10;i>=2;i--){
		r[i]=1e9;
		set<int>s;
		s.insert(1);
		//cout<<i<<" "<<s1[i].size()<<endl;
		int zt=mul[i];
		//cout<<i<<" "<<mul[i]<<endl;
//		cout<<i<<" "<<zt<<" "<<mul[i]<<endl;
//		cout<<i<<endl;
		while(zt!=1){
			int cnt1=0; 
			for(auto j:s){
				//int cnt1=0;
				cnt1++;
				cntt[cnt1]=j;
				
			}
			for(int j=1;j<=cnt1;j++){
				s.insert(cntt[j]*zxzys[zt]);
			}
			int ztt=zt;
			while(ztt%zxzys[zt]==0){
				ztt/=zxzys[zt];
			}
			zt=ztt;
			
		}
	//	puts("fuck"); 
	//if(i==30)cout<<s2[i].size()<<endl; 
		for(auto j:s){
//			cout<<s1[i].size()<<endl;
	//		if(i==30)cout<<j<<endl;
			if(pos1[j])r[i]=min(r[i],pos1[j]);
		}
//		if(i==30){
//			cout<<l[i]<<endl;
//			return 0;
//		}
		pos1[mul[i]]=i;
	}
	//cout<<r[30]<<endl;
	int t;
	scanf("%d",&t);
	int xjy=0;
	while(t--){
		
		ans=0;
		scanf("%d%d",&l1,&r1);
		if(t==4999&&l1==70&&r1==106)xjy=1;
		for(int i=l1;i<=r1;i++)rd[i]=0,mpp[i]=0;
		if(l1==1){
			for(int i=2;i<=r1;i++)ans+=w[i];
			cout<<ans<<endl;
			continue;
		}
		int flag=0;
		for(int i=l1;i<=r1;i++){
			if(mp[i]){
				flag=1;
				break;
			}
		}
		if(flag){
			for(int i=l1;i<=r1;i++){
			//	cout<<i<<" "<<l[i]<<" "<<r[i]<<" "<<w[i]<<endl;
			//mpp[i]=0;
			if(l[i]>=l1&&l[i]<=r1&&(rd[i]==0||mpp[l[i]]==0)){
				//cout<<i<<" l "<<w[i]<<" "<<l[i]<<" "<<r[i]<<endl;
				ans+=w[i];
				mpp[i]=1;
				rd[l[i]]=1;
			}else{
				if(r[i]>=l1&&r[i]<=r1&&(rd[i]==0||mpp[r[i]]==0)){
					//cout<<i<<" r "<<w[i]<<" "<<l[i]<<" "<<r[i]<<endl;
					ans+=w[i];
					mpp[i]=1;
					rd[r[i]]=1;
				}
			}
		}
		for(int i=l1;i<=r1;i++)
{
	if(mpp[i]==0){
		//cout<<i<<" s "<<w[i]<<" "<<l[i]<<" "<<r[i]<<endl;
		ans+=w[i]+1;
	}
		}
		ans-=2;
				}else{
//if(xjy&&t==4784)cout<<l1<<" "<<r1<<endl;
			for(int i=l1;i<=r1;i++){
				dist[i]=1000000000;
				stt[i]=0;
				for(int j=l1;j<=r1;j++)d[i][j]=1000000000;
			}
			for(int i=l1;i<r1;i++){
				for(int j=i+1;j<=r1;j++){
//					int zxgbs=i*j/__gcd(i,j);
//					cout<<i<<" "<<j<<" "<<zxgbs<<endl;
					d[i][j]=min(d[i][j],w[i]+w[j]-w[__gcd(i,j)]);
					d[j][i]=min(d[j][i],w[i]+w[j]-w[__gcd(i,j)]);
					//cout<<i<<" "<<j<<" "<<d[i][j]<<endl;
				}
			}
			prim(l1);
		}
		printf("%d\n",ans);
	}
	return 0;
}