import qualified Data.Vector.Unboxed as U
import qualified Data.Vector.Unboxed.Mutable as UM
import qualified Data.Vector.Generic as G
import Control.Monad
import Data.List

sieveTo :: Int -> U.Vector Bool
sieveTo n = U.create $ do
  isPrime <- UM.replicate n True
  UM.unsafeWrite isPrime 0 False
  UM.unsafeWrite isPrime 1 False
  forM_ [2..n - 1] $ \p -> do
    pIsPrime <- UM.unsafeRead isPrime p
    when pIsPrime $ do
      forM_ [p*2, p*3 .. n - 1] $ \i ->
        UM.unsafeWrite isPrime i False
  return isPrime

isSimilar :: Int -> Bool
isSimilar n = odd n && sieve U.! n && sieve U.! ((n + 1) `div` 2)
  where sieve = sieveTo 100001

countSimilar :: Int -> Int -> Int
countSimilar l r = accum U.! r - accum U.! (l - 1)
  where accum = U.fromList $ scanl1 (+) similars
        similars = map check [0..100001]
        check n
          | isSimilar n = 1
          | otherwise = 0

main :: IO ()
main = do
  q <- readLn
  replicateM_ q $ do
    [l, r] <- mapM readIO . words =<< getLine
    print $ countSimilar l r
