! partialy check
logical function is_reachable(n)
  implicit none
  integer::i, n

  if (n.eq.1) then
     is_reachable = .true.
     return
  end if

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

integer function get_least_step(need_step, temp, N, reach_num)
  implicit none
  integer,allocatable::need_step(:),temp(:)
  integer::num,pcnt,size,step,reach_num,i,j,N, pos
  logical::is_updated

  need_step(1)=1
  do i=1,N
     is_updated = .false.
     do pos=1,N
        pcnt = POPCNT(pos)
        step = need_step(pos)

        if(pos+pcnt.le.N) then
           need_step(pos+pcnt) = MIN(step+1, need_step(pos+pcnt))
           is_updated = .true.
        end if
        if(pos-pcnt.gt.1) then
           need_step(pos-pcnt) = MIN(step+1, need_step(pos-pcnt))
           is_updated = .true.
        end if
     end do
     if (is_updated.eqv..false.) then
        exit
     endif
  end do

  get_least_step = need_step(N)
end function get_least_step

program main
  implicit none
  interface
     logical function is_reachable(N)
       integer::N
     end function is_reachable
     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

  if(N.eq.1) then
     print '(a)',"1"
     return
  else if(is_reachable(N).eqv..false.) 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