import Control.Applicative ((<$>), (<*>))
import Control.Monad
import Data.List
import qualified Data.Vector.Unboxed.Mutable as MV
import qualified Data.Vector.Unboxed as V

main :: IO ()
main = let v = pns 999983 in v `seq` main' v

main' :: V.Vector Int -> IO ()
main' v = do
  n <- getl toInt
  unless (n == 0) $ do
    solve v <$> replicateM n (getl $ wrds toInt) >>= print
    main' v

solve :: V.Vector Int -> [[Int]] -> Int
solve v xs = sum $ map f xs
  where
    f [p,m] = let x = pm p m in if x == 0 then (-1) else x - 1
    pm p m = V.length $ V.dropWhile (< (p - m)) $ V.takeWhile (<= (p + m)) v
    
toInt :: String -> Int
toInt s = read s

toIex :: String -> Integer
toIex s = read s

toDbl :: String -> Double
toDbl s = read s

wrds :: (String -> a) -> String -> [a]
wrds f = map f . words

getl :: (String -> a) -> IO a
getl f = f <$> getLine

getc :: ([String] -> a) -> IO a
getc f = f . lines <$> getContents

pns :: Int -> V.Vector Int
pns = V.map fst . V.filter snd . V.indexed . sieve
  where
    sieve n = V.create $ do
      v <- MV.replicate (n+1) True
      MV.write v 0 False
      MV.write v 1 False
      forM_ (sq 2 n) $ \x -> do
        ip <- MV.read v x
        when ip $ do
          forM_ [x*x, x*(x+1) .. n] $ \y -> do
            MV.write v y False
      return v
    sq s n = if s ^ 2 <= n then s : sq (s+1) n else []