众所周知的斐波那契数列定义如下： $F(0) = F(1) = 1$ $F(n) = F(n - 1) + F(n - 2) \quad \forall n \ge 2$ 这里我们将 $n$ 视为斐波那契数 $F(n)$ 的下标。 自斐波那契的著作《算盘书》（Liber Abaci）出版以来，该数列一直受到研究。到目前为止，人们已经引入了该数列的许多性质。 你曾经对这个数列很感兴趣，但在阅读了大量相关论文后，你认为由于缺乏未被揭示的性质，已经没有必要再对其进行研究了。昨天，你决定转而研究其他数列，例如卢卡斯数列。 昨晚，斐波那契出现在你的梦中。“愚蠢的人类。斐波那契数列中许多重要的性质还没有被任何人研究过，例如，从斐波那契数 347746739 开始……” 你醒来后，除了斐波那契告诉你的前几位数字外，记不清整个数字了。你决定编写一个程序来找出这个数字，以便继续你对斐波那契数列的研究。

输入格式

输入包含多组测试数据。第一行包含一个整数 $T$，表示测试数据的组数（$T \le 50000$）。 对于每组测试数据，只有一行，包含一个由最多 40 位数字组成的非空字符串。且不会有任何不必要的前导零。

输出格式

对于每组测试数据，输出十进制表示以给定数字开头的最小斐波那契数的最小下标。如果不存在下标小于 100000 的斐波那契数满足该条件，则输出 -1 —— 你认为斐波那契想告诉你的事情超出了你的能力范围。

样例

输入 1

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

输出 1

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