import Control.Applicative ((<$>), (<*>))
import Control.Monad
import Data.List

main :: IO ()
main = do
  n <- getl toInt
  unless (n == 0) $ do
    solve <$> replicateM n (getl $ wrds toInt) >>= print
    main

solve :: [[Int]] -> Int
solve 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 = length $ dropWhile (< (p - m)) $ takeWhile (<= (min 999983 (p + m))) pns
    
toInt :: String -> Int
toInt s = read s

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

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

pns :: Integral a => [a]
pns = 2 : 3 : f [] (tail pns) 5
  where
    f ys (x:xs) n = ps ++ f (ys++[x]) xs (x^2+2)
      where
        ip m = all ((/= 0) . (mod m)) ys
        ps = filter ip [n, n+2 .. x^2-2]