main::IO()
main = do
    q <- readLn::IO Int

    queries <- sequence $ replicate q (map read . words <$> getLine)
    mapM_ print $ map (\[a,b] -> (length . filter (/= 2) . filter (a <=) . filter (\x -> factor ((x+1)`div`2) == []) . sieveOfEratosthenes) b) queries


sieveOfEratosthenes :: Int -> [Int]
sieveOfEratosthenes n
    | n < 2 = []
    | n == 2 = [2]
    | otherwise = sieve [x | x <- [2..n]] n

sieve :: [Int] -> Int -> [Int]
sieve [] _ = []
sieve (x:xs) n
    | x^2 > n = x:xs
    | otherwise = x : (sieve [a | a <- xs, a `mod` x > 0] n)

factor ::Int -> [Int]
factor n = filter (\x -> n `mod` x ==0)[2..n-1]
