include <bits/stdc++.h>

include <vector>

include <cstring>

using namespace std;
int N=1000000,d=0;;
bool snt[1000005];
int a[80000];
void sang(){
memset(snt,true,N+4);
snt[0]=snt[1]=false;
for(int i = 2; ii <= N; ++i) {
if(snt[i] == true) {
for(int j =ii; j <= N; j += i){
snt[j] = false;
}
}
}
for(int i=2;i<=N;i++){
if(snt[i]==true){
d++;a[d]=i;
}
}
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(NULL);
sang();
int li,ri;
int q;cin>>q;
while(q--){
cin>>li>>ri;
int *l=lower_bound(a,a+d,li);
int *r=upper_bound(a,a+d,ri);
cout<<r-l<<endl;
}
return 0;
}