import sugar, strutils, queues


let
    n = parseInt readLine stdin

var
    moveCnt = lc[-1 | (i <- 0..<n), int]


proc calcBit(a: int): int =
    var x = a
    while x != 0:
        result += x mod 2
        x = x div 2


proc bfs: int =
    var Q = initQueue[tuple[place, cnt: int]]()
    enqueue Q, (1, 1)
    moveCnt[0] = 1

    while Q.len != 0:
        let q = dequeue Q

        for i in [-1, 1]:
            let q2Place = q.place + calcBit(q.place) * i
            let j = q2Place - 1
            if j in 0..<n and moveCnt[j] < 0:
                moveCnt[j] = q.cnt + 1
                enqueue Q, (q2Place, q.cnt + 1)

    moveCnt[n - 1]


proc main: void =
    echo bfs()


if isMainModule:
    main()