#include<iostream>
#include<vector>
using namespace std;
int main(){
  int max=100001;
  vector<int> a(max,1);
  a[0]=0;
  a[1]=0;
  for(int i=2;i<max;i++){
    for(int j=i*2;j<max;j+=i) a[j]=0;
  }
  
  vector<int> b(max,0);
  for(int i=0;i<max;i++){
     if(i%2==0) continue;
    if(a[i]&&a[(i+1)/2]) b[i]=1;
  }
  
  vector<int> s(max+1,0);
  for(int i=0;i<max;i++) s[i+1]=b[i]+s[i];
  
  int q;
  cin>>q;
  for(int i=0;i<q;i++){
    int l,r;
    cin>>l>>r;
    r++;
    
    cout<<s[r]-s[l]<<endl;
  }
   return 0;
}
