409640: GYM103652 E Power of Function

Memory Limit:0 MB Time Limit:4 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

E. Power of Functiontime limit per test4 secondsmemory limit per test256 mebibytesinputstandard inputoutputstandard output

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.

Input

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.
Output

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.

ExampleInput
5
2 1 1
2 1 2
2 1 4
2 998244353 998244354
10 998244353 998244354
Output
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
Note

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

加入题单

上一题 下一题 算法标签: