Fibonacci Strikes Back

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

\[F_n = \begin{cases} 0 & \text{if }n = 0 \\ 1 & \text{if } n = 1 \\ PF_{n-1} + F_{n-2} & \text{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 \ge 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.

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.

• \(1 \le T \le 10^4\)
• \(1 \le P, m ≤ 10^{18}\)
• \(1 \le k \le 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.

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

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