Revenge of Fibonacci

著名的斐波那契数列定义如下：

$$F_0=F_1=1,\qquad F_n=F_{n-1}+F_{n-2}\quad(n\ge 2).$$

其中，$n$ 是斐波那契数 $F_n$ 的下标。

斐波那契数列自《计算之书》出版以来便得到了广泛研究。你原本认为，这个数列已经没有多少未知性质值得探索，于是决定转而研究卢卡斯数列等其他数列。

然而，斐波那契在梦中告诉你，仍有许多重要性质尚未被发现，并提到了某个斐波那契数。醒来后，你只记得这个数十进制表示的前若干位。

对于每个给定的数字串，请找出十进制表示以该数字串为前缀的斐波那契数，并输出其中最小的下标。若不存在下标小于 $10^5$ 的符合条件的斐波那契数，则输出 $-1$。

输入格式

第一行包含一个整数 $T$，表示测试用例的数量。

接下来 $T$ 行，每行包含一个非空数字串，表示需要查询的前缀。每个数字串至多包含 $40$ 位，且不含多余的前导零。

输出格式

对于第 $i$ 个测试用例，按照以下格式输出答案：

Case #i: ans

其中，ans 为满足条件的最小下标；若不存在下标小于 $10^5$ 的符合条件的斐波那契数，则输出 $-1$。

样例输入

15
1
12
123
1234
12345
9
98
987
9876
98765
89
32
51075176167176176176
347746739
5610

样例输出

Case #1: 0
Case #2: 25
Case #3: 226
Case #4: 1628
Case #5: 49516
Case #6: 15
Case #7: 15
Case #8: 15
Case #9: 43764
Case #10: 49750
Case #11: 10
Case #12: 51
Case #13: -1
Case #14: 1233
Case #15: 22374

数据范围

• $T\le 5\times 10^4$；
• 每个数字串非空，且长度不超过 $40$；
• 输入的数字串不含多余的前导零；
• 只需考虑下标小于 $10^5$ 的斐波那契数。

来源与许可

本题题面与测试数据整理自 BZOJ 2492。

样例 1

输入

15
1
12
123
1234
12345
9
98
987
9876
98765
89
32
51075176167176176176
347746739
5610

输出

Case #1: 0
Case #2: 25
Case #3: 226
Case #4: 1628
Case #5: 49516
Case #6: 15
Case #7: 15
Case #8: 15
Case #9: 43764
Case #10: 49750
Case #11: 10
Case #12: 51
Case #13: -1
Case #14: 1233
Case #15: 22374