Последовательность чисел Фибоначчи определяется следующим образом: \includegraphics{https://static.e-olymp.com/content/37/37f46260faf72584c0548271841480873250631a.jpg} Здесь \textbf{n} - индекс номера числа Фибоначчи \textbf{F(n)}. Эта последовательность хорошо была изучена с момента публикации книги Фибоначчи. С тех пор было обнаружено множество свойств указанной последовательности. Вас заинтересовала эта последовательность после прочтения множества статей о ней. Однако Вы решили больше не заниматься ее исследованием, так как у нее больше не осталось неисследованных свойств. Вчера Вы решили изучать другие последовательности, как например последовательность Люка. Фибоначчи пришел в Ваш сон прошлой ночью. "Глупые человеческие существа. Еще много важных свойств последовательности Фибоначчи не изучены, например начиная с номера \textbf{347746739…}" Вы проснулись, но не смогли вспомнить все число, кроме нескольких его первых чисел, которое сообщил Вам Фибоначчи. Вы решили написать программу, которая сможет найти это число. Так Вы сможете продолжить свои исследования по последовательности Фибоначчи. \InputFile Состоит из нескольких тестов. Первая строка содержит количество тестов \textbf{T} (\textbf{T} ≤ \textbf{50000}). Каждый тест состоит из одной строки, в которой записана непустая последовательность из не более чем \textbf{40} цифр. Ведущие нули в строках отсутствуют. \OutputFile Для каждого теста вывести наименьший индекс наименьшего числа Фибоначчи, десятичная запись которого начинается с заданных цифр. Если никакое число Фибоначчи с индексом меньшим чем \textbf{100000} не удовлетворяет этому условию, то вывести \textbf{-1} -- то что сказал Фибоначчи лежит за пределами Ваших возможностей.