거듭제곱 함수

Bob에게 정의역이 음이 아닌 정수인 함수가 있다.

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

$m$제곱 함수 $f^m(n)$은 다음과 같이 정의한다.

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

Bob은 $l \le n \le r$을 만족하는 정수 $n$이 적어도 하나 있고 $f^m(n) = 1$이 되는 최대의 정수 $m$을 알고 싶어 한다. 또한 이 최대 $m$에 대해 $f^m(n) = 1$을 만족하는 $n$의 최솟값과 최댓값도 구하려 한다. 답을 쉽게 검증할 수 있도록 하기 위해서다.

첫 줄에 테스트 케이스의 수 $T$가 주어진다. 각 테스트 케이스는 정수 $k$, $l$, $r$이 한 줄에 주어진다.

각 테스트 케이스마다 "Case #x: m a b" 형식으로 한 줄씩 출력한다. 여기서 $x$는 1부터 시작하는 테스트 케이스 번호이고, $m$은 가능한 최대 지수, $a$는 그 $m$에 대해 가능한 $n$의 최솟값, $b$는 최댓값이다.

• $1 \le T \le 3 \times 10^5$
• $2 \le k \le 10^{18}$
• $1 \le l \le r \le 10^{18}$
• 각 테스트 케이스마다 해가 존재함이 보장된다.

$k = 2$일 때 $\{f(n)\}_{n=0}^{\infty} = \{0, 0, 1, 2, 2, 4, 3, 6, 4, 8, \dots\}$이고, $\{f^2(n)\}_{n=0}^{\infty} = \{0, 0, 0, 1, 1, 2, 2, 3, 2, 4, \dots\}$이다.