import Data.Ix

main :: IO()
main = do
    _ <- getLine
    lrs <- getContents
    mapM_ (print . count . map read . words) (lines lrs)
        where
            count [l,r] = length $ filter is2017Like $ range (l,r)
            is2017Like 2 = False
            is2017Like n = isPrime n && isPrime ((n + 1) `div` 2)
            isPrime n = mod n 2 /= 0 && all $ map (\m -> mod n m /= 0) [m | m <- [3,5..], m * m <= n]
