Revenge of Fibonacci

The Fibonacci sequence is defined as follows.

• $F(0) = F(1) = 1$
• $F(n) = F(n-1) + F(n-2)$ (for $n \ge 2$)

Here $n$ is called the index of the Fibonacci number $F(n)$.

The Fibonacci sequence has been studied for a very long time, and countless properties are known today. Seonyeong loves studying Fibonacci numbers even more than coding. After reading many papers on them, she came to believe there was no new property left to discover.

That night, Fibonacci appeared in her dream and said: "There is still an important property left unknown. For example, the Fibonacci number 347746739..."

Seonyeong woke up and tried to recall the rest of the digits, but she could not. So she decides to write a program to figure out what that number is.

Given the leading digits of some Fibonacci number, write a program that finds the smallest index among the Fibonacci numbers that start with those digits.

The first line contains the number of test cases $T$ ($T \le 50{,}000$).

Each test case consists of a single line containing the leading digits of some Fibonacci number. This number has at most 40 digits and has no unnecessary leading zeros.

For each test case, print one line in the format Case #x: y, where $x$ is the test case number (starting from 1) and $y$ is the smallest index among the Fibonacci numbers that start with the given digits.

If no Fibonacci number with an index smaller than 100,000 starts with the given digits, print $-1$ in place of $y$.