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