module SegTree = struct
module type Monoid = sig
  type t
  val e : t
  val op : t -> t -> t
end

module Make (S : Monoid) : sig
  type t
  type elt
  (* n要素の単位元からなるセグ木を作る *)
  val make : int -> t
  (* 
   * update i f t
   * i番目の要素にfを適用したセグ木を作る
   *)
  val update : int -> (elt -> elt) -> t -> t
  (*
   * update_range l r f t
   * [l, r)の要素に自己準同型写像fを適用したセグ木を作る
   *)
  val update_range : int -> int -> (elt -> elt) -> t -> t
  (*
   * query l r t
   * [l, r)の要素の積を求める
   *)
  val query : int -> int -> t -> elt
end with type elt = S.t = struct
  type elt = S.t
  (* sizeがセグ木の要素数，dataは要素すべてをモノイドの演算で畳み込んだもの *)
  type t = { size : int; data : elt; body : body lazy_t }
  and body = Leaf | Node of t * t

  let make_node left right =
    { size = left.size + right.size;
      data = S.op left.data right.data;
      body = lazy (Node (left, right)) }

  let rec make n = 
    assert (1 <= n);
    { size = n;
      data = S.e;
      body = lazy
        begin match n with
        | 1 -> Leaf
        | n -> Node (make (n / 2), make ((n + 1) / 2))
        end }

  let rec update i f t =
    assert (0 <= i && i < t.size);
    match t with
    | { body = lazy Leaf } -> { t with data = f t.data }
    | { body = lazy (Node (left, right)) } ->
        if i < left.size then make_node (update i f left) right
        else make_node left (update (i - left.size) f right)

  let rec update_range l r f t =
    assert (0 <= l && l < r && r <= t.size);
    match t with
    | { body = lazy Leaf } -> { t with data = f t.data }
    | { body = lazy (Node (left, right)) } ->
        if l <= 0 && t.size <= r then
          { t with
            data = f t.data;
            body = lazy
              (Node
                (update_range 0 left.size f left,
                 update_range 0 right.size f right)) }
        else if r <= left.size then
          make_node (update_range l r f left) right
        else if left.size <= l then
          make_node left (update_range (l - left.size) (r - left.size) f right)
        else
          make_node
            (update_range l left.size f left)
            (update_range 0 (r - left.size) f right)

  let rec query l r t =
    assert (0 <= l && l < r && r <= t.size);
    match t with
    | { body = lazy Leaf } -> t.data
    | { body = lazy (Node (left, right)) } ->
        if l <= 0 && t.size <= r then t.data
        else if r <= left.size then query l r left
        else if left.size <= l then query (l - left.size) (r - left.size) right
        else S.op (query l left.size left) (query 0 (r - left.size) right)
end
end

module IntSegTree = SegTree.Make (struct
  type t = int
  let e = 0
  let op = ( + )
end)

let eratosthenes n =
  let ps = Array.make n true in
  ps.(0) <- false;
  ps.(1) <- false;
  Array.iteri (fun p -> function
    | false -> ()
    | true ->
        for i = 2 to (Array.length ps - 1) / p do
          ps.(p * i) <- false
        done) ps; ps  

let () =
  let q = Scanf.scanf "%d\n" (fun q -> q) in
  let lrs = Array.init q (fun _ -> Scanf.scanf "%d %d\n" (fun l r -> l, r)) in
  let ps = eratosthenes 100002 in
  let s =
    snd @@ Array.fold_left (fun (i, s) b ->
      (i + 1,
        if b && ps.((i + 1) / 2) then
          IntSegTree.update i (( + ) 1) s
        else s)) (0, IntSegTree.make 100002) ps in
  Array.iter (fun (l, r) ->
    Printf.printf "%d\n" (IntSegTree.query l (r + 1) s)) lrs

Measured memory_bytes: 22656