Магистр Математикус обладает волшебными способностями, которые позволяют ему превращать положительные числа в 1 с помощью следующих операций:
- Если число четное, он может разделить его на 2.
- Если число нечетное, он может увеличить его на 1 или уменьшить на 1.
Сегодня Магистр Математикус задумался над вопросом, какое минимальное количество операций ему необходимо выполнить для превращения числа n
в 1 с использованием его волшебных способностей. Помогите ему ответить на этот вопрос.
Входные данные
Программа получает на вход целое число
n
.
Ограничения на входные данные
Выходные данные
Выведите ответ на задачу.
Примеры
№ |
Входные данные |
Выходные данные |
1 |
8 |
3 |
2 |
7 |
4 |
Запрещенные операторы: for
; while