defmodule Main do
  def main do
    {n, _} =
      IO.read(:line)
      |> Integer.parse()

    n
    |> solve()
    |> IO.puts()
  end

  def solve(n) do
    solve_rec([1], n)
  end

  def solve_rec([h | t], n) do
    c =
      h
      |> Integer.digits(2)
      |> Enum.sum()

    cond do
      h + c == n ->
        ([h | t] |> length) + 1

      true ->
        [
          if(h + c < n && !((h + c) in [h | t]),
            do: solve_rec([h + c | [h | t]], n),
            else: -1
          ),
          if(h - c > 1 && !((h - c) in [h | t]),
            do: solve_rec([h - c | [h | t]], n),
            else: -1
          )
        ]
        |> Enum.filter(&(&1 != -1))
        |> (fn l ->
              cond do
                l |> Enum.empty?() -> -1
                true -> l |> Enum.min()
              end
            end).()
    end
  end
end