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