implicit none
integer q,l,r
!integer,allocatable,dimension(:)::l,r
integer,allocatable,dimension(:)::prime,a,s
integer:: qmax=100000
integer i,j,k,n,m

allocate(prime(qmax),a(qmax),s(qmax))
prime(1)=0
prime(2:qmax)=1
a(:)=0
s(:)=0

do i=2,qmax
if(prime(i).eq.1)then
do j=2*i,qmax,i
prime(j)=0
enddo
endif
enddo

do k=1,qmax
if(prime(k).eq.1 .and. prime((k+1)/2).eq.1)then
a(k)=1
endif
enddo


do n=1,qmax-1
s(n+1)=s(n)+a(n)
enddo


read(5,*)q

do m=1,q
read(5,*) l,r 
write(6,*) s(r+1)-s(l)
enddo


deallocate(prime,a,s)
end