시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
3 초 512 MB 0 0 0 0.000%

## 문제

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.

## 예제 입력 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


## 힌트

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