Маленький морж Клычок очень любит математику. Поэтому, когда ему скучно, он играет с числом, выполняя некоторые операции.
Клычок берет некоторое положительное целое число x, и хочет получить из него единицу. Пока x не равно 1, Клычок повторяет следующее действие: если x нечетное, то он прибавляет к нему 1, иначе он делит x на 2. Клычок знает, что для любого целого положительного числа этот процесс завершается за конечное время.
Сколько действий нужно Клычку, чтобы получить из числа x единицу?
Выходные данные
Выведите необходимое количество действий.
Примечание
Рассмотрим третий пример. Число 101110 четно, значит разделим его на 2. После деления Клычок получает нечетное число 10111 и прибавляет к нему единицу. Число 11000 можно поделить на 2 три раза подряд, и получить число 11. Осталось увеличить число на единицу (получим 100), и затем два раза поделить его на 2. В итоге получается 1.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
1
|
0
|
|
2
|
1001001
|
12
|
|
3
|
101110
|
8
|