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 = myElem n primes
            myElem n (p:ps)
                | n < p = False
                | n == p = True
                | otherwise = myElem n ps
            primes = [2, 3] ++ primes'
                where
                    primes' = 5 : f 1 7 primes'
                    f m s (p : ps) = if p < 100000 then [n | n <- ns, gcd m n == 1] ++ f (m * p) (p * p) ps else [p]
                        where ns = [x + y | x <- [s, s + 6 .. p * p - 2], y <- [0, 4]]
