Помста Фібоначчі
Послідовність чисел Фібоначчі визначається наступним чином:
Тут n - індекс числа Фібоначчі F(n).
Ця послідовність добре вивчена з моменту публікації книги Фібоначчі. Відтоді було виявлено багато властивостей цієї послідовності.
Ви зацікавилися цією послідовністю після прочитання багатьох статей про неї. Однак вирішили більше не займатися її дослідженням, оскільки вважаєте, що всі її властивості вже вивчені. Вчора ви вирішили досліджувати інші послідовності, наприклад, послідовність Люка.
Фібоначчі прийшов до вас у сні минулої ночі. "Дурні людські створіння. Ще багато важливих властивостей послідовності Фібоначчі не вивчені, наприклад, починаючи з номера 347746739…"
Ви прокинулися, але не змогли згадати все число, окрім кількох його перших цифр, які повідомив вам Фібоначчі. Ви вирішили написати програму, яка зможе знайти це число. Так ви зможете продовжити свої дослідження послідовності Фібоначчі.
Вхідні дані
Складається з кількох тестів. Перший рядок містить кількість тестів t (t ≤ 50000).
Кожен тест складається з одного рядка, в якому записана непорожня послідовність з не більше ніж 40 цифр. Провідні нулі в рядках відсутні.
Вихідні дані
Для кожного тесту вивести найменший індекс найменшого числа Фібоначчі, десятковий запис якого починається з заданих цифр. Якщо жодне число Фібоначчі з індексом меншим ніж 100000 не задовольняє цій умові, то вивести -1 — те, що сказав Фібоначчі, лежить за межами ваших можливостей.