{-# LANGUAGE BangPatterns #-}
import qualified Control.Arrow                     as Arrow
import           Data.Bits                         (Bits (unsafeShiftL, unsafeShiftR),
                                                    FiniteBits (countTrailingZeros))
import           Data.Bool                         (bool)
import qualified Data.ByteString.Char8             as BSC8
import qualified Data.List                         as List
import qualified Data.Vector.Fusion.Stream.Monadic as MS
import qualified Data.Vector.Unboxed               as VU
import qualified GHC.Integer.GMP.Internals         as GMP

main :: IO ()
main = do
  n <- readLn :: IO Integer
  if n < 50
    then print $ [0, 1, 2, 3, 3, 5, 5, 7, 7, 7, 7, 11, 11, 13, 13, 7, 7, 17, 8, 19, 19, 19, 7, 23, 23, 23, 8, 8, 8, 29, 8, 31, 8, 8, 8, 8, 8, 37, 8, 8, 8, 41, 8, 43, 8, 8, 8, 47, 8, 14, 8] !! (fromInteger n)
    else if n `mod` 8 == 1 && isPrime (n - 8)
      then print 14
      else print 8

isPrime :: Integer -> Bool
isPrime k
  | k <= 3 = k == 2 || k == 3
  | even k = False
  | otherwise = millerRabin k
  where
    millerRabin :: Integer -> Bool
    millerRabin n
      | n < 18446744073709551616     = millerRabinSmall (fromInteger n)
      | n < 318665857834031151167461 = loop [2,3,5,7,11,13,17,19,23,29,31,37]
      | otherwise                    = loop [2,3,5,7,11,13,17,19,23,29,31,37,41]
      where
        !m = n - 1
        !s = cTZ m 0
        !d = m .>>. s
        cTZ :: Integer -> Int -> Int
        cTZ !i !cnt
          | odd i     = cnt
          | otherwise = cTZ (i .>>. 1) (cnt + 1)
        {-# INLINE cTZ #-}
        check1 :: Integer -> Bool
        check1 a = GMP.powModInteger a d n /= 1
        {-# INLINE check1 #-}
        check2 :: Integer -> Int -> Bool
        check2 a i = (GMP.powModInteger a (d * (1 .<<. i)) n) /= m
        {-# INLINE check2 #-}
        loop [] = True
        loop (a:as)
          | check1 a && allok = False
          | otherwise = loop as
          where
            allok = all (check2 a) [0..(s - 1)]

millerRabinSmall :: Int -> Bool
millerRabinSmall n
  | n < 2047                = loop [2]
  | n < 1373653             = loop [2,3]
  | n < 9080191             = loop [31,73]
  | n < 25326001            = loop [2,3,5]
  | n < 4759123141          = loop [2,7,61]
  | n < 1122004669633       = loop [2,13,23,1662803]
  | n < 2152302898747       = loop [2,3,5,7,11]
  | n < 3474749660383       = loop [2,3,5,7,11,13]
  | n < 341550071728321     = loop [2,3,5,7,11,13,17]
  | otherwise               = loop [2,325,9375,28178,450775,9780504,1795265022]
  where
    !m = n - 1
    !s = countTrailingZeros m
    !d = unsafeShiftR m s
    check3 :: Int -> Bool
    check3 a = powModInt a d n /= 1
    {-# INLINE check3 #-}
    check4 :: Int -> Int -> Bool
    check4 a i = (powModInt a (d * (unsafeShiftL 1 i)) n) /= m
    {-# INLINE check4 #-}
    loop [] = True
    loop (a:as)
      | check3 a && allok = False
      | otherwise = loop as
      where
        allok = all (check4 a) [0..(s - 1)]

powModInt :: Int -> Int -> Int -> Int
powModInt a n mo = fromInteger $ GMP.powModInteger (fromIntegral a) (fromIntegral n) (fromIntegral mo)
{-# INLINE powModInt #-}
-------------------------------------------------------------------------------
type Parser a = BSC8.ByteString -> Maybe (a, BSC8.ByteString)
parseInt :: Parser Int
parseInt = fmap (Arrow.second BSC8.tail) . BSC8.readInt
parse1 :: IO Int
parse1 = readLn
parseN :: Int -> IO (VU.Vector Int)
parseN n = VU.replicateM n parse1
-------------------------------------------------------------------------------
rep :: (Monad m) => Int -> (Int -> m ()) -> m ()
rep n = flip MS.mapM_ (stream 0 n)
{-# INLINE rep #-}

stream :: (Monad m) => Int -> Int -> MS.Stream m Int
stream !l !r = MS.Stream step l
  where
    step x
        | x < r = return $ MS.Yield x (x + 1)
        | otherwise = return MS.Done
    {-# INLINE [0] step #-}
{-# INLINE [1] stream #-}

infixl 8 .>>., .<<.
(.>>.) :: Bits i => i -> Int -> i
(.>>.) = unsafeShiftR
{-# INLINE (.>>.) #-}

(.<<.) :: Bits i => i -> Int -> i
(.<<.) = unsafeShiftL
{-# INLINE (.<<.) #-}