На доске написано число n. Сколько мальчиков нужно вызвать, чтобы на доске получился ноль?

Вызываемые мальчики подходили к доске и должны были писать мелом требуемые цифры и считать их как‑то от правой руки к левой…

Сергей Аксаков. Детские годы Багрова‑внука

На доске написано число n, с которым несколько раз производят следующую операцию: если в записи числа на доске есть хотя бы одна нечётная цифра, то очередной мальчик вычитает из него 1, в противном случае — делит на 2. Сколько мальчиков нужно вызвать, чтобы на доске получился ноль?

Формат входных данных:

Единственная строка входного файла содержит натуральное число n (1≤n≤1018).

Обратите внимание, что входные данные в этой задаче могут превышать возможное значение 32‑битной целочисленной переменной, поэтому необходимо использовать 64‑битные целочисленные типы данных (тип int64 в языке Pascal, тип long long в C и C++, тип long в Java и C#).

Формат выходных данных:

Выведите одно натуральное число — ответ на вопрос задачи.

Замечание:

В примере дано n=25. Число имеет в своей записи нечётную цифру 5, поэтому после первой операции nn уменьшится на 1 и станет равно 24. Число 24 не имеет в своей записи нечётных цифр, поэтому после второй операции nn уменьшится в 2 раза и станет равно 12.

Далее n будет принимать значения: 11,10,9,8,4,2,1 и 0. Всего потребуется 10 операций.