A. Выращиваем бактерии
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вы — большой любитель бактерий. Вам хочется вырастить немного бактерий в коробочке.

Изначально коробочка пуста. Каждое утро можно положить любое количество бактерий в коробочку. Каждую ночь каждая бактерия делится на две бактерии. Когда-нибудь вы надеетесь увидеть ровно x бактерий в коробочке.

Какое минимальное количество бактерий вам суммарно надо положить в коробочку для достижения этой цели?

Входные данные

В единственной строке записано одно целое число x (1 ≤ x ≤ 109) — количество бактерий.

Выходные данные

Единственная строка, содержащая одно целое число — ответ на задачу.

Примеры
Входные данные
5
Выходные данные
2
Входные данные
8
Выходные данные
1
Примечание

В первом примере мы можем положить одну бактерию в коробочку утром первого для, а утром третьего дня в коробочке будет 4 бактерий. Теперь надо положить в коробочку ещё одну бактерию, в результате чего в коробочке окажется 5 бактерий. Мы суммарно добавили 2 бактерии в коробочку, так что ответ равен 2.

Во втором примере мы можем положить одну бактерию утром первого дня, тогда утром четвёртого дня в коробочке будет 8 бактерий. Таким образом, ответ равен 1.