local t={}
for i=2,10^5 do
    t[i]=1
end

local p={}
for i=2,10^5 do
    if t[i]>0 then
        p[i]=1
        for j=2,math.floor(10^5/i) do
            t[i*j]=0
        end
    end
end

local s={}
s[0],s[1]=0,0
for i=2,10^5 do
    if p[i] and p[math.floor((i+1)/2)] then
        s[i]=s[i-1]+1
    else
        s[i]=s[i-1]
    end
end

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