#include<stdio.h>
int main(void){
  char *s="python3 -c\""
"n=10**5;p=[0,0]+[1]*~-n\n"
"for i in range(2,int(n**0.5)+1):\n"
" if p[i]:\n"
"  for j in range(i*2,n+1,i):p[j]=0\n"
"c=[0]\n"
"for i in range(1,n+1):c.append(c[-1]+(i%2and p[i]and p[-~i//2]))\n"
"for _ in[0]*int(input()):l,r=map(int,input().split());print(c[r]-c[l-1])\n"
"\"";
  system(s);
  return 0;
}            