[Wannafly冬令营2018Day2]Fibonacci Strikes Back

内存限制：256 MB 时间限制：4000 ms

在本题中，你需要解决的是关于 $P-$ 斐波那契序列的一个经典问题：

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

现在，给定 $P$ 和 $m$ 以及 $F_{F_n}$ 的十进制表示最低 $k$ 位，你需要找出最小可能的 $n$ 使得 $n \geq m$ 且 $F_{F_n}$ 的十进制表示最低 $k$ 位存在并如上所示，或者确定这样的解是不存在的。

当 $P = 1$ 时 ${F_{F_n}}_{n = 0}^{\infty} = {0, 1, 1, 1, 2, 5, 21, 233, 10946, 5702887, 139583862445, \cdots}$。

当 $P = 2$ 时 ${F_{F_n}}_{n = 0}^{\infty} = {0, 1, 2, 29, 13860, 44560482149, \cdots}$。

输入包含多组测试数据。第一行包含一个整数 $T$，表示测试数据的组数。随后的内容是各组测试数据。对于每组测试数据：

仅一行，包含两个整数 $P$, $m$ 和一个长度为 $k$ 的数字串，这个串是 $F_{F_n}$ 的十进制表示最低 $k$ 位。

对于每组测试数据，输出一行Case #x: y，其中x是测试数据的编号（从 $1$ 开始编号），而在答案存在时y是最小可能的 $n$，在答案不存在时y是 $-1$。

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

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

C1646 [Wannafly冬令营2018Day2]Fibonacci Strikes Back