import Control.Monad
import Control.Monad.ST
import Data.List
import Control.Monad.Trans.State.Strict
import Data.Char (isSpace)
import Data.Maybe (fromJust)
import qualified Data.Vector.Unboxed as UV
import qualified Data.Vector.Unboxed.Mutable as MV

import qualified Data.ByteString.Char8 as B

type Parser a = StateT B.ByteString Maybe a

parseInt :: Parser Int
parseInt = StateT (B.readInt . B.dropWhile isSpace)

parseInt2 :: Parser (Int,Int)
parseInt2 = liftM2 (,) parseInt parseInt

parse :: Parser [(Int,Int)]
parse = do
    q<-parseInt
    replicateM q parseInt2

pr=2:q
q=3:5:7:3#q
m#(a:b:x)=[n|n<-[a^2,a^2+2..b^2-2],gcd n m<2]++(m*b)#(b:x)

prs = takeWhile (<100000) pr

csum = UV.create $ do
    pv <- MV.replicate 100000 0:: ST s (MV.STVector s Int)
    sv <- MV.replicate 100000 0:: ST s (MV.STVector s Int)
    forM_ prs $ \p -> MV.unsafeWrite pv p 1
    forM_ prs $ \p -> do
        a <- MV.unsafeRead pv ((p+1)`div`2)
        when (a == 1) $ MV.unsafeWrite sv p 1
    forM_ [1..100000] $ \i ->
        MV.unsafeWrite sv i =<< (+) <$> MV.unsafeRead sv (i-1) <*> MV.unsafeRead sv i
    return sv

main = do
    lrs<- fromJust.evalStateT parse <$> B.getContents::IO[(Int,Int)]
    --
    putStr $ unlines $ map (show.(\(l,r)-> (csum UV.! r) - (csum UV.! (l-1)))) lrs
