#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define ll long long
using namespace std;
const int N=1e7;
int l,r;
bool zsf[N+5];
int zs[N+5];
int zss;
bool kx[N+5];
int qzh[N+5];
int sum=0;
int q;
int main(){
	freopen("a.in","r",stdin);
	freopen("a.out","w",stdout);
	zsf[0]=1;
	zsf[1]=1;
	for(ll i=2;i<=N;i++){
		if(zsf[i]==0){
			zss++;
			zs[zss]=i;
			sum++;
		}
		for(ll j=1;zs[j]*i<=N&&j<=zss;j++){
			zsf[i*zs[j]]=1;
			if(zsf[i]==0){
				kx[i*zs[j]]=1;
			}
			if(!(i%zs[j]))break;
		}
		if(kx[i]==1){
			sum++;
		}
		qzh[i]=sum;
	}
	scanf("%d",&q);
	for(int i=1;i<=q;i++){
		scanf("%d%d",&l,&r);
		printf("%d\n",qzh[r]-qzh[l-1]);
	}
	return 0;
}