Валера считает, что число красивое, если оно равно 2k или -2k для некоторого целого k (k ≥ 0). Недавно учитель математики попросил Валеру представить число n в виде суммы красивых чисел. Так как Валера очень жадный, он хочет использовать для выполнения этого задания минимально возможное количество красивых чисел.
Помогите Валере, найдите это количество. Другими словами, если мы рассмотрим все разложения числа n на красивые слагаемые, то нужно найти размер разложения, в котором меньше всего слагаемых.
Выходные данные
Выведите единственное целое число — минимальное количество красивых чисел, сумма которых равна n.
Примечание
В первом примере n = 2 является красивым числом.
Во втором примере n = 7, и Валера может разложить его в сумму 23 + ( - 20).
В третьем примере n = 109 раскладывается в сумму четырех слагаемых следующим образом: 27 + ( - 24) + ( - 22) + 20.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
10
|
1
|
|
2
|
111
|
2
|
|
3
|
1101101
|
4
|