module que_module
    implicit none

    type que
        private
        integer::s=1,t=1
        integer,allocatable::contents(:)
    contains
        procedure::is_empty
        procedure::poll
        procedure::peek
        procedure::put
    end type que

    interface que
        module procedure init
    end interface

contains

    type(que) function init(n)
        integer::n
        allocate(init%contents(n))
    end function init

    logical function is_empty(q)
        class(que)::q
        logical::ret
        ret=((q%s).eq.(q%t))
        is_empty=ret
    end function is_empty

    integer function poll(q)
        class(que)::q
        poll=q%contents(q%s)
        q%s=q%s+1
    end function poll

    integer function peek(q)
        class(que)::q
        peek=q%contents(q%s)
    end function peek

    subroutine put(q,v)
        class(que)::q
        integer::v
        q%contents(q%t)=v
        q%t=q%t+1
    end subroutine put

end module que_module

integer function bitcount(n)
    implicit none
    integer,intent(in)::n
    integer::n_
    bitcount=0

    n_=n
    do while(n_>0)
        if(mod(n_,2)==1)bitcount=bitcount+1
        n_=n_/2
    end do

end function bitcount


program main
    use que_module
    implicit none

    interface
        integer function bitcount(n)
            integer::n
        end function bitcount
    end interface

    integer::i,j,k,l,m,n,dx,inf=30000
    integer::a(10000)
    type(que)::q

    q=que(40000)
    read*,n
    do i=1,size(a)
        a(i)=inf
    end do
    a(1)=1

    call q%put(1)

    do while(.not.q%is_empty())
        i=q%poll()
        dx=bitcount(i)
        do j=i-dx,i+dx,2*dx
            if(j<0.or.j>n)cycle
            if(a(j)/=inf)cycle
            a(j)=a(i)+1
            call q%put(j)
        end do
    end do

    if(a(n)==inf)a(n)=-1
    print*,a(n)

end program