Допустим, мы имеем пару чисел (a, b). Мы можем получить новую пару чисел вида (a + b, b) или (a, a + b) из данной. Назовем такое действие шагом.
Пусть начальная пара чисел — (1,1). Ваша задача — найти число k, наименьшее количество шагов, необходимых чтобы получить из (1,1) пару, в которой хотя бы одно число равно n.
Выходные данные
Выведите единственное число k.
Примечание
Из пары (1,1) можно за три хода получить пару, содержащую 5: (1,1) → (1,2) → (3,2) → (5,2).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
|
3
|
|
2
|
1
|
0
|