open System

[<AutoOpen>]
module Cin =
    let read f = stdin.ReadLine() |> f
    let reada f = stdin.ReadLine().Split() |> Array.map f

    let readInts() =
        read string
        |> Seq.toArray
        |> Array.map (fun x -> Convert.ToInt32(x.ToString()))

module Util =
    let strRev s =
        s
        |> Seq.rev
        |> Seq.map string
        |> String.concat ""

let esieve upper =
    let res = Array.create (upper + 1) true
    res.[0] <- false
    res.[1] <- false
    for n in 2 .. upper do
        if res.[n] then
            for m in 2 .. upper do
                let l = int64 n * int64 m
                if l <= int64 upper then res.[int l] <- false
    res

[<EntryPoint>]
let main _ =
    let Q = read int
    let lr = Array.zeroCreate Q
    for i in 0 .. Q - 1 do
        lr.[i] <- reada int

    let lim = int 1e5 + 1
    let sieve = esieve lim
    let vs = Array.zeroCreate lim
    for i in 0 .. lim - 1 do
        if sieve.[i] && sieve.[(i + 1) / 2] then vs.[i] <- 1
    let acc = Array.zeroCreate (lim + 1)
    for i in 0 .. lim - 1 do
        acc.[i + 1] <- acc.[i] + vs.[i]

    for i in 0 .. Q - 1 do
        let [| l; r |] = lr.[i]
        let ans = acc.[r + 1] - acc.[l]
        printfn "%d" ans
    0 // return an integer exit code
