$n = gets.to_i

def bfs(node, n)
  q = []
  searched = Array.new(n+1, -1)
  searched[node] = 1
  q.push(node)
  while !q.empty?
    node = q.shift
    delta = node.to_s(2).split("").map(&:to_i).inject(:+)
    
    if node-delta >= 1 && searched[node-delta] < 0
      searched[node-delta] = searched[node] + 1
      q.push(node-delta)
    end

    if node+delta <= n && searched[node+delta] < 0
      searched[node+delta] = searched[node] + 1
      q.push(node+delta)
    end
  end
  return searched
end

puts bfs(1, $n)[$n]