B. Пары чисел
ограничение по времени на тест
1 second
ограничение по памяти на тест
256 megabytes
ввод
stdin
вывод
stdout

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

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

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

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

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

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

Примеры
Входные данные
5
Выходные данные
3
Входные данные
1
Выходные данные
0
Примечание

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