409638: GYM103652 C Fibonacci Strikes Back
Description
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.
InputThe 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.
ExampleInput7 1 3 1 1 4 1 1 6 01 1 1 45 2 1 0482149 998 244 353 998244 1 353Output
Case #1: 3 Case #2: 6 Case #3: 101 Case #4: 10 Case #5: 5 Case #6: -1 Case #7: 233Note
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\}$$$.