Помста Фібоначчі#3093
Послідовність Фібоначчі визначається так:
Тут — це індекс числа Фібоначчі .
Ця послідовність вивчається з часу публікації книги Фібоначчі. Було відкрито багато властивостей цієї послідовності.
Ви зацікавилися цією послідовністю після прочитання багатьох статей про неї. Але ви вирішили не вивчати її далі, оскільки подумали, що всі її властивості вже відкриті. Учора ви вирішили вивчати інші послідовності, наприклад, послідовність Лукаса.
Минулої ночі Фібоначчі з’явився вам у сні. "Нерозумні люди. Багато важливих властивостей послідовності Фібоначчі ще не були досліджені, наприклад, починаючи з числа "
Ви прокинулися, але змогли згадати лише перші кілька цифр числа, яке назвав Фібоначчі. Ви вирішили написати програму, щоб знайти це число й продовжити свої дослідження послідовності Фібоначчі.
Є кілька тестових випадків. У першому рядку задано кількість тестів (t \leq 50000).
Кожен тест складається з одного рядка, що містить непорожній рядок не більше ніж з цифр. Рядки не містять провідних нулів.
Для кожного тесту виведіть мінімальний індекс найменшого числа Фібоначчі, десятковий запис якого починається із заданої послідовності цифр. Якщо жодне число Фібоначчі з індексом меншим за не задовольняє цю умову, виведіть -1 — отже, те, що сказав вам Фібоначчі, поза межами ваших можливостей.
Приклад 1