409640: GYM103652 E Power of Function

Bob has a function

$$$$$$f(n) = \begin{cases} \frac{n}{k} & \texttt{if $n \bmod k = 0$} \\ n - 1 & \texttt{otherwise} \end{cases}\text{,}$$$$$$

which is defined for all non-negative integers.

Denote the $$$m$$$-th power of this function as $$$f^m(n)$$$ such that

$$$$$$f^m(n) = \begin{cases} f^{m - 1}(f(n)) & \texttt{if $m > 0$} \\ n & \texttt{otherwise} \end{cases}\text{.}$$$$$$

He would like to know the maximum possible integer $$$m$$$ meeting the condition that there exists at least one integer $$$n$$$ such that $$$l \leq n \leq r$$$ and $$$f^m(n) = 1$$$. Besides, please help him find out the minimum and the maximum $$$n$$$ for the maximum possible $$$m$$$ so that he could easily validate your answer is correct.

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 three integers $$$k, l, r$$$.

• $$$1 \leq T \leq 3 \times 10^5$$$
• $$$2 \leq k \leq 10^{18}$$$
• $$$1 \leq l \leq r \leq 10^{18}$$$
• It is guaranteed that solution exists for each test case.

For each test case, output a line containing "Case #x: m a b" (without quotes), where x is the test case number starting from $$$1$$$, m is the maximum possible exponent, a is the minimum possible argument, and b is the maximum possible argument with respect to m.

5
2 1 1
2 1 2
2 1 4
2 998244353 998244354
10 998244353 998244354

Case #1: 0 1 1
Case #2: 1 2 2
Case #3: 2 3 4
Case #4: 35 998244353 998244354
Case #5: 55 998244354 998244354

When $$$k = 2$$$, $$$\{f(n)\}_{n = 0}^{\infty} = \{0, 0, 1, 2, 2, 4, 3, 6, 4, 8, \ldots\}$$$, and $$$\{f^2(n)\}_{n = 0}^{\infty} = \{0, 0, 0, 1, 1, 2, 2, 3, 2, 4, \ldots\}$$$.