import Data.Array
import Data.Array.ST
import Control.Monad

eratos::Int->[Int]
eratos 0 = []
eratos 1 = []
eratos 2 = [2]
eratos n = sieve [2..n] n
              where
                sieve::[Int]->Int->[Int]
                sieve [] _     =[]
                sieve (x:xs) k = if  x^2 > k then (x:xs) else x:(sieve (filter (\y->mod y x /= 0) xs) k)



create_eratos_flag::Int->Array Int Bool
create_eratos_flag n =runSTArray $ do
                    ar<-newArray (2,n) False
                    forM_ (eratos n) (\p -> writeArray ar p True)
                    return ar

create_ans_sheet::Int->Array Int Int
create_ans_sheet n = let flag = create_eratos_flag n in
                     let ans_ls = fold_map_ls (\count -> \i -> count+if (flag!i) && (flag!(div (1+i) 2)) then 1 else 0) 0 [3..n] in
                     listArray (1,n) (0:0:ans_ls)


fold_map_ls::(a->b->a)->a->[b]->[a]
fold_map_ls  _ _ []     = []
fold_map_ls  f i (x:xs) = (f i x):(fold_map_ls f (f i x) xs)

ans::Int->Int->Int
ans l r = (create_ans_sheet 100000)!r -(create_ans_sheet 100000)!(max (l-1) 1)

n_treat::Int->IO()
n_treat 0 = return ()
n_treat n = do
  lrc<-getLine
  let l:r:[]= map read (words lrc)
  print (ans l r)
  n_treat (n-1)

main::IO()
main=do
  n<-getLine
  n_treat (read n)
