Задача 5. Треугольник Фибоначчи ≡

Условие

Числа Фибоначчи — элементы бесконечной числовой последовательности 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, … , в которой первые два числа равны 1 и 1, а каждое последующее число равно сумме двух предыдущих чисел.

Треугольник Фибоначчи — это треугольник, составленный из чисел на основе чисел Фибоначчи. Две стороны этого треугольника образуют последовательность Фибоначчи. Каждое число является суммой двух чисел выше по левой или правой диагонали. Ниже на рисунке приведены несколько первых строк треугольника:

Тимофей исследует свойства этого треугольника. Ему необходимо знать, встретится ли нужное ему натуральное число в этом треугольнике, и если да, то в какой по порядку строке это произойдет?

Формат входных данных

В единственной строке записано натуральное число n.

Формат выходных данных

Выведете одно натуральное число — номер строки треугольника, в которой впервые встретится данное число. Если число в треугольнике не встретится никогда, выведите  − 1.

Ограничения

1 ≤ n ≤ 10¹⁸

Система оценки и описание подзадач

Баллы за каждую подзадачу начисляются только в случае, если все тесты этой подзадачи успешно пройдены.

Подзадача 1: 1 ≤ n ≤ 10³, баллы: 30.

Подзадача 2: нет дополнительных ограничений, баллы: 70.

Пояснения к примерам

Число 2 первый раз встречается в третьей строке треугольника, число 10 — в седьмой, число 12 не встречается вообще.

Примеры тестов

2

3

10

7

12

-1