import Data.Bits
import Control.Monad.State
import qualified Data.Vector.Unboxed as U
import Debug.Trace
import Data.List

main = do
  n <- readLn
  print $ evalState (bitDice [1] n) (1, U.fromList []) 


bitDice :: [Int] -> Int -> State (Int, U.Vector Int) Int
bitDice [] _ = return $ -1
bitDice sl n  =  do
  (c, visited)  <- get   
  {-if k `U.elem` visited
      then bitDice ks n --return $ [min c $ minimum $ evalState (bitDice ks n) (c, visited)-}
  if n `elem` sl
    then return c
    else do 
      let
        nexts x = filter (\y -> y > 0 && y <= n && y `U.notElem` visited) [x + popCount x, x - popCount x]
      do 
        put (c + 1, visited U.++ U.fromList sl)
        bitDice (nub . concat $ map nexts sl) n