import Data.Array.ST
import Data.Array.Unboxed
import Data.Array.IArray
import Control.Monad
import Control.Monad.ST
main = interact $ unlines.map (unwords.map show.(\x -> [lessPrimeSearch x,overPrimeSearch x]).read).lines

prime = sieve 999999

sieve :: Int -> UArray Int Bool
sieve n = runSTUArray $ do
    t <- newArray (0,n) True
    writeArray t 0 False
    writeArray t 1 False
    sequence_ [writeArray t i False | i <- [4,6..n]]
    let sqn = (floor.sqrt.fromIntegral) (n::Int)
    sequence_ (actions t sqn n)
    return t

actions :: STUArray s Int Bool -> Int -> Int -> [ST s ()]
actions t k m = [readArray t i >>= (flip when) (writeArray t j False) | i <- [3,5..k],j <- [i*i,i*(i+2)..m]]

lessPrimeSearch n = if prime ! (n-1) then n-1
                                     else lessPrimeSearch (n-1)

overPrimeSearch n = if prime ! (n+1) then n+1
                                     else overPrimeSearch (n+1)