local mce, mfl, msq, mmi, mma = math.ceil, math.floor, math.sqrt, math.min, math.max

local primes = {}
local allnums = {}
local a = 100000
allnums[1] = 0
for i = 2, a do allnums[i] = 1 end
for i = 2, a do
  if(allnums[i] == 1) then
    table.insert(primes, i)
    local lim = math.floor(a / i)
    for j = 2, lim do
      allnums[j * i] = 0
    end
  end
end
local map = {}
map[1] = 0
map[2] = 0
for i = 3, a do
  if(i % 2 == 1 and allnums[i] == 1 and allnums[mfl((i + 1) / 2)] == 1) then
    map[i] = map[i - 1] + 1
  else
    map[i] = map[i - 1]
  end
end
local q = io.read("*n")
for i = 1, q do
  local l, r = io.read("*n", "*n")
  if(l == 1) then print(map[r])
  else print(map[r] - map[l - 1]) end
end
