let q = Scanf.scanf " %d" @@ (+) 0
let rmax = ref 0
let lrs = Array.init q @@ fun _ -> Scanf.scanf " %d %d" @@ fun a b ->
  rmax := max !rmax b; a, b
let is_prime n =
  if n <= 1 then false
  else
    let rec loop i =
      if i * i > n then true
      else if n mod i = 0 then false
      else loop @@ i + 1 in
    loop 2
let sums = Array.make (!rmax + 1) 0
let f n = if n mod 2 = 1 && is_prime n && is_prime @@ (n + 1) / 2 then 1 else 0
let _ =
  for i = 0 to !rmax - 1 do sums.(i + 1) <- sums.(i) + f (i + 1) done;
  let f (l, r) =
    Printf.printf "%d\n" @@ sums.(r) - sums.(l - 1)
  in
  Array.iter f lrs