program prob4
    implicit none
    integer::p(100005), a(100005)
    integer::i, j, Q, l, r

    p = 0
    do i = 2, 100000
        if(p(i) == 0) then
            do j = 2*i, 100000, i
                p(j) = 1
            end do
        end if
    end do

    a = 0
    do i = 3, 100000
        if(p(i) == 0 .and. p((i+1)/2) == 0) then
            a(i) = a(i-1) + 1
        else
            a(i) = a(i-1)
        end if
    end do
    
    read(*,*) Q
    do i = 1, Q
        read(*,*) l, r
        write(*,*) a(r) - a(l-1)
    end do
    stop
end program