import Control.Monad
import Data.Set as S hiding (foldl, map)

count :: Int -> Int -> Int
count l r =
  like2017s!!r - like2017s!!l

like2017s :: [Int]
like2017s =
  scanl (+) 0 l
  where 
    l = map (\x -> if elem x p && elem (div (x+1) 2) p then 1 else 0) [0,1..10^5]
    p = primes [2,3..10^5]

primes :: [Int] -> [Int]  
primes = S.toList . (seive 2) . S.fromList  

seive :: Int -> Set Int-> Set Int
seive p xs  
  | p*p > S.findMax xs = xs  
  | otherwise = seive (p+1) $ foldl (\acc x -> S.delete x acc) xs [2*p,3*p..q]  
  where q = S.findMax xs
                               
solve :: [(Int,Int)] -> [Int]
solve [] = []
solve ((l,r):lrs) =
  count l r : solve lrs

main = do
  q <- read <$> getLine
  lrs <- replicateM q $! (\(x:y:[]) -> (read x,read y)) . words <$> getLine
  forM_ (solve lrs) $ print