import           Control.Monad
import qualified Control.Monad.ST            as ST
import qualified Data.ByteString.Char8       as BS
import           Data.Maybe
import qualified Data.Vector.Unboxed         as V
import qualified Data.Vector.Unboxed.Mutable as VM

readInt = fst . fromJust . BS.readInt
readIntList = map readInt . BS.words
getInt = readInt <$> BS.getLine
getIntList = readIntList <$> BS.getLine

-- generates a vector of prime numbers <= n
primes n = ST.runST $ do
    v <- VM.new (n+1)
    VM.write v 0 0
    VM.write v 1 0
    forM_ [2..n] $ \i -> VM.write v i i
    let sqrtN = ceiling $ sqrt $ fromIntegral n
    forM_ [2..sqrtN] $ \i -> do
      x <- VM.read v i
      when (x > 0) (forM_ [2..(n`div`i)] $ \j -> VM.write v (i*j) 0)
    v' <- V.freeze v
    return $ V.filter (> 0) v'

bisectLeft :: Ord a => (Int -> a) -> a -> Int -> Int -> Int
bisectLeft f x lo hi
  | lo >= hi  = lo
  | f mid < x = bisectLeft f x (mid+1) hi
  | otherwise = bisectLeft f x lo mid
  where
    mid = lo + (hi - lo) `div` 2

main = do
  q <- getInt

  d <- VM.new (10^5 + 1)
  VM.write d 0 (0::Int)

  let ps = primes (10^5)

      isPrime x = let i = bisectLeft (\i -> ps V.! i) x 0 (V.length ps - 1)
                  in x == ps V.! i

      like2017 x = isPrime x && isPrime ((x+1) `div` 2)

      prepD :: Int -> Int -> IO ()
      prepD i n | i > 10^5 = return ()
                | otherwise = do
                    let n' = n + if like2017 i then 1 else 0
                    VM.write d i n'
                    prepD (i+1) n'

  prepD 1 0

  replicateM_ q $ do
    [l, r] <- getIntList
    x <- VM.read d (l-1)
    y <- VM.read d r
    print (y-x)