#include<iostream>
using namespace std;
int br[1000005]={0};
int main(){
int k, a, b, i, v;
int fl=0;
cin>>k;
for(i=1; i<=k; i++)
{
    cin>>a>>b;
        if(a==2 || a==3 || a==1) {a=5; br[i]+=2;}
        if(a%2==0) a++;
    while(a<=b)
   {
            for(int kd=3; kd<=a/2+1; kd+=2)
                if(a%kd==0) {fl=1; break; }
            if(fl==0) br[i]++;
        a+=2;
        fl=0;
    }    
}

for(i=1; i<=k; i++)
    cout<<br[i]<<endl;
return 0;
}