import           Data.Bits                   (Bits(popCount))
import           Data.IntSet                 (IntSet)
import qualified Data.IntSet                 as IntSet
import qualified Data.Vector.Unboxed         as VU

popCountVector :: Int -> VU.Vector Int
popCountVector n = VU.generate (n + 1) popCount
{-# NOINLINE popCountVector #-}

main :: IO ()
main = do
  n <- readLn :: IO Int
  print $ bfs [1] [] n 1 IntSet.empty (popCountVector n)

bfs :: [Int] -> [Int] -> Int -> Int -> IntSet -> VU.Vector Int -> Int
bfs []     [] _ _ _  _   = -1
bfs []     nx g c st vec = bfs nx [] g (c + 1) st vec
bfs (b:bs) nx g c st vec
  |  b < 1
  || b > g
  || IntSet.member b st  = bfs bs nx g c st vec
  |  b == g = c
  |  otherwise
  = let
      x   = vec VU.! b
      st2 = IntSet.insert b st
    in bfs bs ((b + x) : (b - x) : nx) g c st2 vec