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

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

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