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

count l r =
  length $ takeWhile (<=r) $ dropWhile (<l) like2017s

like2017s =
  [ x |x<-p, elem (div (x+1) 2) p  ]
  where p = primes [2..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) $ (\e -> print e)
 

