program D_solution

implicit none
integer :: Q,l(10**5),r(10**5),n
integer :: i,j,is_prime(10**5)

read(*,*) Q
do i = 1, Q
  read(*,*) l(i),r(i)
enddo

  is_prime(1) = 0
do i = 2, 10**5
  is_prime(i) = 1
  do j = 2, int((i)**0.5)
    if(mod(i,j) == 0) then
      is_prime(i) = 0
    endif
  enddo
enddo

do i=1,Q
  n = 0
  do j=l(i),r(i),2
    if(is_prime(j) == 1 .and. is_prime(int((j+1)/2)) == 1) then
	n = n + 1
    endif
  enddo
  write(*,*) n
enddo
end program