coins i n sk = if sk + i > n then [] else sk + i : coins (i + 1) n (sk + i)

f i n cs
    | i == length cs            = False
    | any (== n - cs !! i) cs   = True
    | otherwise                 = f (i + 1) n cs

solve cs n
    | any (==n) cs  = 1
    | f 1 n cs      = 2
    | otherwise     = 3

main = do
    n <- readLn :: IO Int
    print $ solve (coins 1 n 0) n