Виртуальное соревнование – это способ прорешать прошедшее соревнование в режиме, максимально близком к участию во время его проведения. Поддерживается только ICPC режим для виртуальных соревнований.
Если вы раньше видели эти задачи,
виртуальное соревнование не для вас – решайте эти задачи в архиве.
Если вы хотите просто дорешать задачи, виртуальное соревнование не для вас – решайте эти задачи в архиве.
Запрещается использовать чужой код, читать разборы задач и общаться по содержанию соревнования с кем-либо.
Допустим, мы имеем пару чисел (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).