import strutils
import sequtils
import heapqueue
import bitops

let N = stdin.readLine.parseInt
var dist = newSeqWith(N+1, 123456789)
var hq = initHeapQueue[(int, int)]()
hq.push((1, 1))
while hq.len != 0:
  let (c, v) = hq.pop
  if dist[v] <= c:
    continue
  dist[v] = c
  if v == N:
    echo c
    quit()
  let popcnt = popcount(v)
  for i in @[-1, 1]:
    if 0 < v + i * popcnt and v + i * popcnt <= N and dist[v] + 1 < dist[v + i * popcnt]:
      push(hq, ((dist[v] + 1), v + i * popcnt))
echo -1