시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
4 초 512 MB 1 1 1 100.000%

## 문제

Bob has a function

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

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)) & \text{if }m > 0 \\ n & \text{otherwise}\end{cases}$

He would like to know the maximum possible integer $m$ meeting the condition that there exists at least one integer $n$ such that $l \le n \le 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$.

## 출력

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.

## 제한

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

## 예제 입력 1

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


## 예제 출력 1

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, \dots\}$, and $\{f^2(n)\}_{n=0}^{\infty} = \{0, 0, 0, 1, 1, 2, 2, 3, 2, 4, \dots\}$.