PROGRAM MAIN
    IMPLICIT NONE

    INTEGER :: N
    INTEGER, ALLOCATABLE :: A(:)
    INTEGER, ALLOCATABLE :: QUE(:)
    INTEGER :: HEAD, TAIL
    INTEGER :: I, K
    INTEGER :: LEFT, RIGHT

    READ *, N

    ALLOCATE(A(N), SOURCE = -1)
    ALLOCATE(QUE(N))

    HEAD = 1
    TAIL = 1

    QUE(1) = 1
    A(1) = 1

    DO WHILE(HEAD <= TAIL)

        I = QUE(HEAD)
        HEAD = HEAD + 1

        K = POPCNT(I)

        LEFT = I - K
        RIGHT = I + K

        IF (LEFT > 0 .AND. A(LEFT) == -1) THEN
            A(LEFT) = A(I) + 1
            TAIL = TAIL + 1
            QUE(TAIL) = LEFT
        END IF

        IF (RIGHT <= N .AND. A(RIGHT) == -1) THEN
            A(RIGHT) = A(I) + 1
            TAIL = TAIL + 1
            QUE(TAIL) = RIGHT
        END IF
    
    END DO

    PRINT *, A(N)
END PROGRAM MAIN