integer function get_reach_num(n)
  implicit none
  integer::i, n, reach_num
  get_reach_num = 0

  if (n.eq.1) then
     get_reach_num = 1
     return
  end if

  do i=max(1,n-(31-LEADZ(10000))), n
     if (n.eq.POPCNT(i)+i) then
        get_reach_num = get_reach_num + 1
     end if
  end do
end function get_reach_num


module stack
  integer::top
  integer,allocatable::contents(:)
contains
  subroutine construct(N)
    integer::N
    allocate(contents(N))
    top = 0
  end subroutine construct
end module stack

logical function is_empty()
  use stack
  is_empty = top.eq.0
end function is_empty

integer function pop()
  use stack
  pop = contents(top)
  top = top - 1
end function pop

integer function get_size()
  use stack
  get_size = top
end function get_size

subroutine push(n)
  use stack
  integer::n
  top = top + 1
  contents(top) = n
end subroutine push

integer function get_least_step(need_step, temp, N, reach_num)
  use stack
  implicit none
  interface
     integer function pop()
     end function pop
     integer function get_size()
     end function get_size
     logical function is_empty()
     end function is_empty
  end interface
  integer,allocatable::need_step(:),temp(:)
  integer::num,popcount,size,step,reach_num,i,j,N, pos
  call construct(N)

  call push(1)
  need_step(1)=1

  do i=1,N
     size = get_size()
     do j=1, size
        temp(j) = pop()
     end do

     do j=1, size
        pos = temp(j)
        popcount = POPCNT(pos)
        step = need_step(pos)

        if(pos+popcount.eq.N)  then
           get_least_step = step+1
           return
        end if

        if(pos+popcount.le.N) then
           if (need_step(pos+popcount) .gt. step+1) then
              need_step(pos+popcount) = step + 1
              call push(pos+popcount)
           end if
        end if
        if(pos-popcount.gt.1) then
           if (need_step(pos-popcount) .gt. step+1) then
              need_step(pos-popcount) = step + 1
              call push(pos-popcount)
           end if
        end if
     end do
     if(is_empty().eqv..true.) then
        exit
     end if
  end do

  get_least_step = need_step(N)
end function get_least_step

program main
  implicit none
  interface
     integer function get_reach_num(n)
       integer::n
     end function get_reach_num
     integer function get_least_step(need_step, temp,N, reach_num)
       integer,allocatable::need_step(:),temp(:)
       integer::N,reach_num
     end function get_least_step
  end interface
  integer::N, least_step, reach_num
  integer,allocatable::need_step(:),temp(:)

  read *,N

  reach_num = get_reach_num(N)
  if(N.eq.1) then
     print '(a)',"1"
     return
  else if(reach_num.eq.0) then
     print '(a)',"-1"
     return
  endif


  allocate(need_step(N))
  allocate(temp(N))

  need_step=N
  temp=0

  least_step = get_least_step(need_step,temp,N, reach_num)
  if (least_step.eq.N) then
     print '(a)',"-1"
  else
     print '(i0)',least_step
  end if
end program main