在这个问题中，你需要解决一个关于 $P$-Fibonacci 序列的著名问题：

$$ F_n = \begin{cases} 0 & \text{if } n = 0 \\ 1 & \text{if } n = 1 \\ P F_{n-1} + F_{n-2} & \text{otherwise} \end{cases} $$

现在给定 $P$、$m$ 以及 $F_n$ 的最低 $k$ 位十进制数字，请你确定满足 $n \ge m$ 且 $F_n$ 的最低 $k$ 位十进制数字与给定字符串相符的最小可能的 $n$，如果不存在则输出 -1。

输入格式

输入包含多组测试数据。第一行包含一个整数 $T$，表示测试数据的组数。接下来描述所有测试数据。对于每组测试数据：

唯一的一行包含两个整数 $P$、$m$ 和一个长度为 $k$ 的字符串，该字符串仅由数字组成，表示 $F_n$ 的最低 $k$ 位十进制数字。注意该字符串可能包含前导零。

• $1 \le T \le 10^4$
• $1 \le P, m \le 10^{18}$
• $1 \le k \le 18$
• 所有测试数据中 $k$ 的总和不超过 $10^4$。
• 保证对于每组测试数据，$P$ 与 $10^{18}$ 的最大公约数小于 5。

输出格式

对于每组测试数据，输出一行 “Case #x: y”，其中 x 是从 1 开始的测试数据编号，y 是满足条件的最小可能的 $n$，如果不存在则 y 为 -1。

样例

输入 1

7
1 3 1
1 4 1
1 6 01
1 1 45
2 1 0482149
998 244 353
998244 1 353

输出 1

Case #1: 3
Case #2: 6
Case #3: 101
Case #4: 10
Case #5: 5
Case #6: -1
Case #7: 233

说明

当 $P = 1$ 时，$\{F_n\}_{n=0}^{\infty} = \{0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, \dots\}$。 当 $P = 2$ 时，$\{F_n\}_{n=0}^{\infty} = \{0, 1, 2, 5, 12, 29, 70, 169, 408, 985, 2378, 5741, 13860, \dots\}$。