program main
  implicit none
  logical::PRIME(10**5)=.true.
  integer::cnt(0:10**5)=0
  integer::i,j
  integer::Q,l,r
  Prime(1)=.false.
  do i=2,10**5
    if(.not.PRIME(i))cycle
    j=2
    do while(j*i<=10**5)
      PRIME(j*i)=.false.
      j=j+1
    end do
    if(Prime((i+1)/2))then
      cnt(i)=1
    endif
  end do
  do i=2,10**5
    cnt(i)=cnt(i)+cnt(i-1)
  end do
  
  read*,Q
  do i=1,Q
    read*,l,r
    print"(i0)",cnt(r)-cnt(l-1)
  end do
end program main