import Control.Monad
import Data.Maybe
import qualified Data.ByteString.Char8 as BS
import Data.List
import qualified Data.Vector.Unboxed as VU

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

main = do
    q <- getInt
    lrs <- replicateM q $ do
        [l, r] <- getIntList
        return (l, r)
    let ps = VU.fromList . scanl' (+) (0 :: Int) $ map (\p -> if isPrime p && isPrime ((p+1) `div` 2) then 1 else 0) [1..100000]
        ans = map (\(l,r) -> ps VU.! r - ps VU.! (l-1)) lrs
    mapM_ print ans

primes = primes'
  where
    primes' = [2, 3, 5] ++ f 5 7 (drop 2 primes')
    f m s (p:ps) = [n | n <- ns, gcd m n == 1] ++ f (m * p) (p * p) ps
      where
        ns = [x + y | x <- [s,s + 6 .. p * p - 2], y <- [0, 4]]

isPrime n = (n > 1) && isPrime' primes
  where
    isPrime' (x:xs)
      | x * x > n = True
      | rem n x == 0 = False
      | otherwise = isPrime' xs