import Control.Monad
import Control.Applicative
import System.IO

isPrime :: Int -> Bool
isPrime num
    | num == 1 = False
    | otherwise = null(filter (\x -> num `mod` x == 0) [2..floor(sqrt(fromIntegral num))])

solve :: [Int] -> Int
solve [l,r] = length[x | x<-[l..r], isPrime x, isPrime $ (x+1) `div` 2, odd x]

rl :: IO ()
rl=do
  e<-isEOF
  if e
    then return ()
    else do
      ss <- (map read . words) <$> getLine -- input: 123 456 789
-- ss = [123, 456, 789]
      putStrLn $ show $ solve ss
      rl

main = do
  q <- readLn :: IO Int
  rl