E. Число Фибоначчи
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
stdin
вывод
stdout

У Джона Доу есть список всех чисел Фибоначчи по модулю 1013. Этот список бесконечен, он начинается с чисел 0 и 1. Каждое число в этом списке, кроме двух первых, является суммой двух предыдущих по модулю 1013, то есть список Джона получается из списка чисел Фибоначчи заменой каждого числа в нем его остатком от деления на 1013.

Теперь Джон загадал число f (0 ≤ f < 1013), и хочет найти его первое вхождение в описанный выше список. Помогите Джону, найдите номер первого вхождения числа f в список или сообщите, что число f в списке не встречается.

Нумерация в списке ведется с нуля. Под номером 0 в списке Джона стоит число 0, под номером 1 — число 1, под номером 2 — число 1, под номером 3 — число 2, под номером 4 — число 3 и так далее. Таким образом, начало списка выглядит следующим образом: 0, 1, 1, 2, 3, 5, 8, 13, 21, ...

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

В первой строке записано единственное целое число f (0 ≤ f < 1013) — число, позицию которого в списке нужно найти.

Пожалуйста, не используйте спецификатор %lld для чтения или записи 64-х битовых чисел на С++. Рекомендуется использовать потоки cin, cout или спецификатор %I64d.

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

Выведите единственное число — номер первого вхождения заданного числа в список Джона или -1, если это число не входит в список Джона.

Примеры
Входные данные
13
Выходные данные
7
Входные данные
377
Выходные данные
14