program main
    use,intrinsic :: iso_fortran_env
    implicit none
    integer(int32):: q,i,j,l,r
    integer(int32):: cnt_like2017(0:100000)
    integer(int32), allocatable:: ans(:)
    logical:: is_prime(100000), is_like2017(100000)
    is_prime(:) = .true.
    is_prime(1) = .false.

    do i=2,size(is_prime)
        if (is_prime(i)) then
            j=2
            do while(i*j <= size(is_prime))
                is_prime(i*j) = .false.
                j=j+1
            end do
        end if
    end do
    
    do i=1,100000,2
        is_like2017(i) = is_prime(i) .and. is_prime((i+1)/2)
    end do

    cnt_like2017(:) = 0
    do i=1,100000
        cnt_like2017(i) = cnt_like2017(i-1)
        if (is_like2017(i)) cnt_like2017(i)=cnt_like2017(i)+1
    end do


    read*, q
    allocate(ans(q), source=0)
    do i=1,q
        read*, l,r
        ans(i) = cnt_like2017(r) - cnt_like2017(l-1)
    end do

    print'(i0)', ans(:)
end program main