import strutils, sequtils, sets, algorithm
proc trfm(i: int): int = i.toBin(16).count('1')
let
  N = stdin.readLine.parseInt
var
  ttl, mini1, mini2 = newSeq[int](N)
  x = 1
mini1 = @[0]
ttl[0] = 1

proc go(x: int) =
  for i0 in mini1.sorted(cmp, Descending):
    var i = i0
    while true:
      let pre = i
      i += (i + 1).trfm * x
      if x == 1:
        if i >= N: break
      else:
        if i <= 0: break
      if ttl[i] == 0:
        ttl[i] = ttl[pre] + 1
        mini2.add i
  if mini2.len == 0: echo -1; quit()
  swap(mini1, mini2)
  mini2 = @[]

while ttl[^1] == 0:
  go(x)
  x *= -1

echo ttl[^1]