RECURSIVE SUBROUTINE SUGOROKU(A, N, I)
    IMPLICIT NONE
    INTEGER :: N, A(N), I
    INTEGER :: BITTO, TMP

    BITTO = 0
    TMP = I

    DO WHILE (TMP > 0)
        BITTO = BITTO + MOD(TMP, 2)
        TMP = TMP / 2
    END DO

    IF (I - BITTO > 0 .AND. (A(I - BITTO) == -1 .OR. A(I - BITTO) > A(I) + 1)) THEN
        A(I - BITTO) = A(I) + 1
        CALL SUGOROKU(A, N, I - BITTO)
    END IF

    IF (I + BITTO <= N .AND. (A(I + BITTO) == -1 .OR. A(I + BITTO) > A(I) + 1)) THEN
        A(I + BITTO) = A(I) + 1
        CALL SUGOROKU(A, N, I + BITTO)
    END IF
END SUBROUTINE SUGOROKU

PROGRAM MAIN
    IMPLICIT NONE
    INTEGER :: N
    INTEGER, ALLOCATABLE, DIMENSION(:) :: A

    READ *, N
    ALLOCATE(A(N), SOURCE = -1)

    ! PRINT *, A(:)

    A(1) = 1

    CALL SUGOROKU(A, N, 1)

    PRINT *, A(N)
END PROGRAM MAIN