Вызываемые мальчики подходили к доске и должны были писать мелом требуемые цифры и считать их как-то от правой руки к левой...
Сергей Аксаков, <<Детские годы Багрова-внука>>.
На доске написано число \(n\), с которым несколько раз производят следующую операцию: если в записи числа на доске есть хотя бы одна нечётная цифра, то очередной мальчик вычитает из него 1, в противном случае — делит на 2. Сколько мальчиков нужно вызвать, чтобы на доске получился ноль?
Формат входных данных
Единственная строка входного файла содержит натуральное число \(n\) (\(1 \le n \le 10^{18}\)).
Обратите внимание, что входные данные в этой задаче могут превышать возможное значение 32-битной целочисленной переменной, поэтому необходимо использовать 64-битные целочисленные типы данных (тип int64 в языке Pascal, тип long long в C и C++, тип long в Java и C#).
Формат выходных данных
Выведите одно натуральное число — ответ на вопрос задачи.
Замечание
В примере дано \(n = 25\). Число имеет в своей записи нечётную цифру \(5\), поэтому после первой операции \(n\) уменьшится на \(1\) и станет равно \(24\).
Число \(24\) не имеет в своей записи нечётных цифр, поэтому после второй операции \(n\) уменьшится в \(2\) раза и станет равно \(12\).
Далее \(n\) будет принимать значения: \(11\), \(10\), \(9\), \(8\), \(4\), \(2\), \(1\) и \(0\). Всего потребуется \(10\) операций.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
25
|
10
|