Олимпиадный тренинг

Задача . B. Пары чисел


Допустим, мы имеем пару чисел (a, b). Мы можем получить новую пару чисел вида (a + b, b) или (a, a + b) из данной. Назовем такое действие шагом.

Пусть начальная пара чисел — (1,1). Ваша задача — найти число k, наименьшее количество шагов, необходимых чтобы получить из (1,1) пару, в которой хотя бы одно число равно n.

Входные данные

Входные данные содержат единственное целое число n (1 ≤ n ≤ 106).

Выходные данные

Выведите единственное число k.

Примечание

Из пары (1,1) можно за три хода получить пару, содержащую 5: (1,1)  →  (1,2)  →  (3,2)  →  (5,2).


Примеры
№Входные данныеВыходные данные
1
5
3
2
1
0
Статистика успешных решений по компиляторам
 Кол-во
С++5