local function getprimes(x)
  local primes = {}
  local allnums = {}
  for i = 1, x do allnums[i] = true end
  for i = 2, x do
    if allnums[i] then
      table.insert(primes, i)
      local lim = x // i
      for j = 2, lim do
        allnums[j * i] = false
      end
    end
  end
  allnums[1] = false
  return allnums
end

local isprimes = getprimes(100000)
local cnt = {0, 0}
for i = 3, 100000, 2 do
  if isprimes[i] and isprimes[(i + 1) // 2] then
    cnt[i] = cnt[i - 1] + 1
  else
    cnt[i] = cnt[i - 1]
  end
  cnt[i + 1] = cnt[i]
end
local q = io.read("*n")
for iq = 1, q do
  local l, r = io.read("*n", "*n")
  local z = cnt[r]
  if 1 < l then
    z = z - cnt[l - 1]
  end
  print(z)
end
