-- 解説、他の回答参照

import qualified Data.Set as S
import Data.Bits

solve :: S.Set Int -> S.Set Int -> Int -> Int -> Int
solve flag queue i n
    | queue == S.empty  = -1
    | elem n queue  = i
    | otherwise     = solve flag' queue' (i + 1) n
    where
        inc = S.filter (\x -> x > 0 && x <= n) $ S.map (\x -> x + popCount x) queue
        dec = S.filter (\x -> x > 0 && x <= n) $ S.map (\x -> x - popCount x) queue
        queue' = S.difference (S.union inc (S.difference dec inc)) flag
        flag' = S.union flag queue'

main = readLn >>= print . solve (S.singleton 1) (S.singleton 1) 1