import qualified Data.Array.ST    as S
import qualified Data.Array       as S
import qualified Control.Monad.ST as S
import Control.Monad

import qualified Data.ByteString.Char8 as B
import qualified Data.IntSet as Set
import Data.Maybe
import Data.List

import Data.Array.Unboxed

genPrimes :: Int -> [Int]
genPrimes n = map fst . filter snd . zip [2..] $ S.runST ( do
    isPrime <- S.newArray (2, n) True :: S.ST s (S.STUArray s Int Bool)
    forM_ [2..div n 2] $ \i ->
        S.writeArray isPrime (2*i) False
    forM_ [3,5..n] $ \i -> do
        a <- S.readArray isPrime i
        when a (forM_ [2..div n i] $ \l ->
            S.writeArray isPrime (i*l) False)
    S.elems <$> S.freeze isPrime)

main :: IO ()
main = do
    let m = 100000
    q <- read <$> getLine :: IO Int
    qs <- replicateM q ((\[a,b]->(a,b)) . 
        map (fst . fromJust . B.readInt) . B.words <$> B.getLine) :: IO [(Int,Int)]
    let primes = Set.fromList (genPrimes m)
        isPrime n = n `Set.member` primes
        primeCnt = listArray (0, m) . drop 1 $ scanl (+) 0
                   [if odd i && isPrime i && isPrime ((i+1) `div` 2) then 1 else 0|i<-[0..m]] :: UArray Int Int
    mapM_ (\(l,r) -> print $ primeCnt!r - primeCnt!(l-1)) qs