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}$$ 他想知道满足“存在至少一个整数 $n$ 使得 $l \le n \le r$ 且 $f^m(n) = 1$”的最大的整数 $m$。此外，请帮他找出在最大可能的 $m$ 下，满足条件的最小 $n$ 和最大 $n$，以便他能轻松验证你的答案是否正确。

输入格式

输入包含多组测试数据。第一行包含一个整数 $T$，表示测试数据的组数。接下来描述所有测试数据。对于每组测试数据： 仅一行，包含三个整数 $k, l, r$。 $1 \le T \le 3 \times 10^5$ $2 \le k \le 10^{18}$ $1 \le l \le r \le 10^{18}$ 保证每组测试数据均有解。

输出格式

对于每组测试数据，输出一行 “Case #x: m a b”（不含引号），其中 $x$ 是从 1 开始的测试数据编号，$m$ 是最大可能的指数，$a$ 是在 $m$ 下满足条件的最小参数，$b$ 是在 $m$ 下满足条件的最大参数。

样例

输入 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

说明

当 $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\}$。