import qualified Data.ByteString.Char8 as BS
import Data.Maybe
import qualified Data.Set as Set

primes :: Int -> [Int]
primes n = 2 : f [3] [3,5..n]
  where
    f [] _ = []
    f (x:xs) ys =
        let (ps, qs) = span (< x^2) ys
         in ps ++ f (xs ++ ps) [z | z <- qs, z `rem` x /= 0]

solve :: Set.Set Int -> Int -> Int -> Int
solve s l r = length $ filter same2017 [l..r]
  where
    isPrime = flip Set.member s
    same2017 n = isPrime n && isPrime ((n+1) `div` 2)

main :: IO ()
main = do
    _ <- getLine
    lr <- map ((\[a,b] -> (a,b))
        . map (fst . fromJust . BS.readInt) . BS.words) . BS.lines
        <$> BS.getContents :: IO [(Int,Int)]
    let mx = maximum $ map snd lr
        tbl = Set.fromList $ primes (mx + 1)
    mapM_ (print . uncurry (solve tbl)) lr 
