#include<iostream>
using namespace std;
int main(){
long long k, broqch, prostichislabroqch, proverka;
cin>>k;
bool naistinalieprosto;
long long a[k], b[k], broiprostivintervala[k];
for(broqch=0;broqch<k;broqch++){
    cin>>a[broqch]>>b[broqch];
    broiprostivintervala[broqch]=0;
}
for(proverka=0;proverka<k;proverka++){
    for(broqch=a[proverka];broqch<b[proverka]+1;broqch++){
        naistinalieprosto=true;
        if(broqch>1){
            for(prostichislabroqch=2;prostichislabroqch<=broqch/2;prostichislabroqch++){
                if((broqch%10)%2==0 && broqch>2){
                    naistinalieprosto=false;
                }else{
                    if(broqch%prostichislabroqch==0){
                        naistinalieprosto=false;
                    }
                }
            }
        }else{
            naistinalieprosto=false;
        }
        if(naistinalieprosto){
            broiprostivintervala[proverka]=broiprostivintervala[proverka]+1;
        }
    }
}
for(broqch=0;broqch<k;broqch++){
    cout<<broiprostivintervala[broqch]<<endl;
}
return 0;
}