Q=io.read("n")
l={}
r={}
for i=1,Q do
  l[i]=io.read("n")
  r[i]=io.read("n")
end
function prime(o)
  local res=true
  if o==1 or o==2 then
    return res
  elseif o>2 then
    for i=2,o-1 do
      if o%i==0 then
        res=false
      end
    end
    return res
  end
end
for i=1,Q do
  local count=0
  for j=l[i],r[i] do
    if prime(j) and prime((j+1)//2) then
      count=count+1
    end
  end
  print(count)
end