409638: GYM103652 C Fibonacci Strikes Back

In this problem, you need to solve a well-known problem about $$$P$$$-Fibonacci sequence:

$$$$$$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}$$$$$$

Now given $$$P$$$, $$$m$$$ and the lowest $$$k$$$ decimal digits of $$$F_{F_n}$$$, you are asked to determine the minimum possible $$$n$$$ such that $$$n \geq m$$$ and $$$F_{F_n}$$$ has at least $$$k$$$ lowest decimal digits as given above, or report it is impossible otherwise.

The input contains several test cases. The first line contains an integer $$$T$$$ indicating the number of test cases. The following describes all test cases. For each test case:

The only line contains two integers $$$P$$$, $$$m$$$ and a string of length $$$k$$$, consisting of only digits, which represents the lowest $$$k$$$ decimal digits of $$$F_{F_n}$$$. Note the string may contain leading zeros.

• $$$1 \leq T \leq 10^4$$$
• $$$1 \leq P, m \leq 10^{18}$$$
• $$$1 \leq k \leq 18$$$
• The sum of $$$k$$$ in all test cases does not exceed $$$10^4$$$.
• It is guaranteed that the greatest common divisor of $$$P$$$ and $$$10^{18}$$$ is less than $$$5$$$ for each test case.

For each test case, output a line containing "Case #x: y" (without quotes), where x is the test case number starting from $$$1$$$, and y is the minimum possible $$$n$$$ to this test case if it exists, or y is $$$-1$$$ otherwise.

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

When $$$P = 1$$$, $$$\{F_{F_n}\}_{n = 0}^{\infty} = \{0, 1, 1, 1, 2, 5, 21, 233, 10946, 5702887, 139583862445, \ldots\}$$$.

When $$$P = 2$$$, $$$\{F_{F_n}\}_{n = 0}^{\infty} = \{0, 1, 2, 29, 13860, 44560482149, \ldots\}$$$.