$N = gets.to_i
$steps = Array.new($N, -1)

def popcount(n)
  n.digits(2).sum
end

def carol(n, curSteps)
  return if n <= 0 || n > $N

  if $steps[n-1] == -1 || $steps[n-1] > curSteps
     $steps[n-1] = curSteps
     counts = popcount(n)
     carol(n + counts, curSteps+1)
     carol(n - counts, curSteps+1)
  end
end

carol(1, 1)
puts $steps[$N-1]