void main(){
  import std.stdio, std.string, std.conv, std.algorithm;

  const mx=1_000_00+5;
  auto isPrime=new bool[](mx);
  auto sub=new int[](mx);

  isPrime[2]=true;
  for(int i=3; i<=1_000_00; i+=2){
    for(int j=3; j*j<=i; j+=2){
      if(i%j==0) goto hell;
    }
    isPrime[i]=true;
    if(isPrime[(i+1)/2]) sub[i]=1;
    hell:;
  }

  int[] a;
  for(int i=3; i<=1_000_00; i++)if(sub[i]) a~=i;
  int q; rd(q);
  while(q--){
    int l, r; rd(l, r);
    int cnt=0;
    foreach(e; a){
      if(l<=e && e<=r) cnt++;
    }
    writeln(cnt);
  }
}

void rd(T...)(ref T x){
  import std.stdio, std.string, std.conv;
  auto l=readln.split;
  assert(l.length==x.length);
  foreach(i, ref e; x){
    e=l[i].to!(typeof(e));
  }
}
void wr(T...)(T x){
  import std.stdio;
  foreach(e; x) write(e, " ");
  writeln();
}