
open Scanf
open Printf

let flip f x y = f y x

let rec range a b = if a >= b then [] else a :: range (a+1) b

let read_int () = scanf " %d" (fun x -> x)
let rec read_ints n = if n = 0 then [] else let i = read_int () in i :: read_ints (n-1)

let rec for_iter a b f = if a >= b then [] else let x = f a in x :: for_iter (a+1) b f
let rec for_iter_ a b f = if a >= b then () else (f a; for_iter_ (a+1) b f)
let rec for_iterr_ a b f = if a <= b then () else (f a; for_iterr_ (a-1) b f)

let gen_table ubound =
  let res = Array.make ubound 1 in
  res.(0) <- 0; res.(1) <- 0;
  for_iter_ 2 ubound (fun i ->
    if res.(i) > 0 then for_iter_ 2 (ubound / i) @@ fun j -> res.(i*j) <- 0);
  for_iterr_ ((ubound+1)/2) 1 (fun a ->
    let i = 2*a-1 in
    res.(i) <- if res.(i) = 1 && res.((i+1)/2) = 1 then 1 else 0);
  res.(2) <- 0;
  for_iter_ 1 ubound (fun i -> res.(i) <- res.(i) + res.(i-1));
  res

let () =
  let q = read_int () in
  let rs = for_iter 0 q (fun _ -> let l = read_int () in let r = read_int () in (l, r)) in
  let table = gen_table 200010 in
  flip List.iter rs (fun (l, r) -> printf "%d\n" (table.(r) - table.(l-1)))


