#include <iostream>
using namespace std;
bool prost[1000000];
long long prosti[1000];
void prostit(){
long long i,x,h=0;
for(x=2;x<1000000;x++){
    if((x==2||x%2!=0)&&(x==3||x%3!=0)&&prost[x]==true){
        h++;

for(i=x*x;i<=1000000;i=i+x){
prost[i]=false;
}
}
}
}
long long check(long long a,long long b){
long long i,z=0;
for(i=a;i<b;i++){
if(prost[i]==true){
z++;
}
}
return z;
}
int main(){
    for(long long h=0;h<1000000;h++){
     prost[h]=true;
    }
    prostit();
    prost[1]=false;
long long a,b,k,i;
cin>>k;

for(i=0;i<k;i++){
cin>>a>>b;
cout<<check(a,b)<<endl;
}
}