Scanf.scanf "%d" (fun q ->
    let isprime =
        let p = Array.init 100001 (fun i -> if i < 2 then 0 else i) in
        let rec loop_i i =
            let rec loop_j j =
                if j > 100000 then loop_i (i + 1) else (
                    p.(j) <- 0; loop_j (j + i)
                )
            in
            if i * i <= 100000 then loop_j (i * i)
        in
        loop_i 2;
        (fun i -> p.(i) <> 0)
    in
    let b = Array.init 100001 (fun i ->
        if i mod 2 = 0 then 0 else
        if isprime i && isprime ((i + 1) / 2) then 1 else 0
    )
    in
    let a = Array.make 100001 0 in
    let rec loop j =
        if j < 100000 then (a.(j) <- a.(j - 1) + b.(j); loop (j + 1))
    in
    loop 1;

    for i = 1 to q do
        Scanf.scanf " %d %d" (fun l r -> Printf.printf "%d\n" @@ a.(r) - a.(l - 1))
    done
)