{-# LANGUAGE RankNTypes #-}
import Control.Monad
import Control.Monad.ST
import Data.Bits
import Data.Maybe
import qualified Data.ByteString.Lazy.Char8 as B
import qualified Data.Vector.Unboxed as V
import qualified Data.Vector.Unboxed.Mutable as VM


pMax = 100000

-- bsReadInts bstr
--   Reads and returns the list of int separated by space.
--   Usually bstr is one line, but can consist of two or more lines.
bsReadInts :: B.ByteString -> [Int]
bsReadInts = map (fst . fromJust . B.readInt) . B.words

-- sieve : the infinite list of prime numbers
sieve :: [Int]
sieve = 2 : sieve_sub [2] [3..]

sieve_sub :: [Int] -> [Int] -> [Int]
sieve_sub (n:yet) cand =
  let
    (cnfmd, rem) = span (< n*n) cand
    newcand = filter (\i -> i `mod` n /= 0) rem
  in cnfmd ++ sieve_sub (yet ++ cnfmd) newcand

data BIT s a = BIT Int (VM.MVector s a)
  -- BIT size vec, where the indices of vec is from 0 to size - 1

bitLsbAdd :: Int -> Int
bitLsbAdd k = k + (k .&. (-k))

bitLsbOff :: Int -> Int
bitLsbOff k = k .&. complement (k .&. (-k))

-- bitEmpty size
--   Creates the BIT that represents [0 | i < size].
bitEmpty :: (Num a, VM.Unbox a) => Int -> ST s (BIT s a)
bitEmpty size = VM.replicate size 0 >>= return . BIT size

-- bitFromPairs ps
--   Creates the BIT for ps, where (n, a_n) \in ps.
--   Each i should appear in ps at most once.
bitFromPairs :: (Num a, VM.Unbox a) => [(Int, a)] -> ST s (BIT s a)
bitFromPairs ps = bitFromPairsWithSize (1 + (maximum (map fst ps))) ps

-- bitFromParisWithSize size ps
--   The same as bitFromPairs, but with size given.
bitFromPairsWithSize :: (Num a, VM.Unbox a) =>
                        Int -> [(Int, a)] -> ST s (BIT s a)
bitFromPairsWithSize size ps = do
  bit <- bitEmpty size
  forM_ ps $ \(n, x) -> bitUpd bit n x
  return bit

-- bitBuild ns ... Creates the BIT for ns,
--   i.e., a_n = 1 if n is in ns;  a_n = 0 otherwise.
--   Each n should appear in ns at most once.
bitFromList :: (Num a, VM.Unbox a) => [Int] -> ST s (BIT s a)
bitFromList ns = bitFromPairs [(n, 1) | n <- ns]

-- bitBuildWithSize ns ... Creates the BIT for ns, with size given
bitFromListWithSize :: (Num a, VM.Unbox a) => Int -> [Int] -> ST s (BIT s a)
bitFromListWithSize size ns = bitFromPairsWithSize size [(n, 1) | n <- ns]

-- bitFix ... Immutablize a BIT
bitFix :: (VM.Unbox a) => (forall s. ST s (BIT s a)) -> V.Vector a
bitFix act = V.create $ do
  BIT _ vec <- act
  return vec

-- bitSum bit n
--   Calculates \Sum{ a_i | 0 <= i < n }
bitSum :: (Num a, VM.Unbox a) => BIT s a -> Int -> ST s a
bitSum (BIT _ vec) n = 
  foldM g 0 $ takeWhile (> 0) $ iterate bitLsbOff n
  where g sum i = (+ sum) <$> (VM.read vec (i - 1))

-- bitFixSum vec n
--   Returns \Sum{ a_i | 0 <= i < n }
--   Vector vec is immutablized vector part of a BIT.
bitFixSum :: (Num a, VM.Unbox a) => V.Vector a -> Int -> a
bitFixSum vec n =
  sum $ map ((vec V.!) . (+ (-1))) $ takeWhile (> 0) $ iterate bitLsbOff n

-- bitUpd bit n diff
--   Updates bit with a_n -> a_n + diff
bitUpd :: (Num a, VM.Unbox a) => BIT s a -> Int -> a -> ST s ()
bitUpd (BIT size vec) n diff = forM_ indices act
  where indices = takeWhile (<= size) (iterate bitLsbAdd (n + 1))
          -- indices = {k + 1 | k is a necessary index}
        act k = VM.modify vec (+ diff) (k - 1)

intersectOL :: (Ord a) => [a] -> [a] -> [a]
intersectOL [] _ = []
intersectOL _ [] = []
intersectOL (a:as) (b:bs) | a == b = a : intersectOL as bs
                          | a <  b = intersectOL as (b:bs)
                          | a >  b = intersectOL (a:as) bs

solve :: Int -> [[Int]] -> [Int]
solve valQ lrs = [query l r | [l, r] <- lrs]
  where
    like2017 = intersectOL sieve [2 * p - 1 | p <- sieve]
    vbit = bitFix (bitFromListWithSize pMax (takeWhile (< pMax) like2017))
    query :: Int -> Int -> Int
    query l r = bitFixSum vbit (r + 1) - bitFixSum vbit l

main :: IO ()
main = do
  conts <- B.getContents
  let [valQ] : lrs = map bsReadInts (B.lines conts)
      answer = solve valQ lrs
  putStr (unlines (map show answer))


Measured memory_bytes: 4860