local t={}
t[0],t[1],t[2]=0,0,0
for i=3,10^5,2 do
    local check=true
    for j=2,math.sqrt(i) do
        if i%j==0 then
            check=false
            break
        end
    end
    if check then
        for j=2,math.sqrt((i+1)//2) do
            if ((i+1)//2)%j==0 then
                check=false
                break
            end
        end
    end
    t[i]=t[i-1]+(check and 1 or 0)
    t[i+1]=t[i]
end

local q=io.read("n")
for i=1,q do
    local l,r=io.read("n","n")
    print(t[r]-t[l-1])
end