Revenge of Fibonacci#3093
The Fibonacci sequence is defined as follows:
Here, is the index of the Fibonacci number .
This sequence has been studied since the publication of Fibonacci's book. Many properties of this sequence have been discovered.
You became interested in this sequence after reading many articles about it. However, you decided not to study it further, since you thought all its properties had already been discovered. Yesterday, you decided to study other sequences instead, such as the Lucas sequence.
Last night, Fibonacci appeared in your dream. "Foolish human beings. Many important properties of the Fibonacci sequence have not yet been studied, for example, starting from the number "
You woke up, but could only remember the first few digits of the number that Fibonacci told you. You decided to write a program to find this number so you can continue your research on the Fibonacci sequence.
There are several test cases. The first line contains the number of test cases (t \leq 50000).
Each test case consists of a single line containing a non-empty string of at most digits. There are no leading zeros in the strings.
For each test case, output the smallest index of the smallest Fibonacci number whose decimal notation begins with the given digits. If no Fibonacci number with index less than satisfies this condition, output -1 — what Fibonacci told you is beyond your ability.
Example 1