瓦西亚正在准备他的信息学高考，并在他的一本教科书中发现了以下题目：“图书馆里所有的书都采用相同的格式。一本书包含 400 页，每页包含 40 行，每行恰好有 80 个印刷字符。共有 25 种不同的字符：22 个字母、句号、逗号和空格。计算编码单本书内容所需的比特数。”

瓦西亚认为，该题目的作者假设所有字符都必须使用相同数量的比特进行编码。因此，要编码 25 种不同的字符，每个字符必须使用 5 个比特。但这样的编码方式意味着存储了不必要的冗余信息。

如果已知不同的字符及其组合在文本中出现的频率不同，那么使用变长编码（例如哈夫曼编码）将是有意义的。但作者并没有提供必要的信息，因此瓦西亚假设所有字符及其组合在文本中出现的频率均等，并使用固定长度的比特进行编码。

瓦西亚进一步思考，意识到如果对字符组（而不是单个字符）进行编码，可以部分消除这些无用信息。

例如，当对连续三个字符组成的字符组进行编码时，可能出现的组合数为 $25^3 = 15625$。那么 14 个比特就足够编码这些组合。这样，每个字符平均只需要 $4\frac{2}{3}$ 个比特，而不是作者所假设的 5 个比特。

瓦西亚想知道这是否是一种可以无限逼近 $\log_2 25 \approx 4.64385619$ 的方法。但随后他想到，这种编码是用于有限长度的消息的。如果消息的长度不能被所编码的字符组长度整除，消息将自动用空格填充，直到字符组的数量成为整数。此外，由于技术原因，无法使用过长的字符组。

瓦西亚决定编写一个程序，来确定在给定参数下编码消息时，字符组的最佳大小。请帮助瓦西亚编写这个程序。

输入格式

第一行包含一个整数 $T$ — 测试用例的数量（$1 \le T \le 10^4$）。接下来是测试用例的描述，每个测试用例占一行。

对于每个测试用例，提供三个整数：$N$ — 消息字符集的大小，$L$ — 消息的字符长度，以及 $K$ — 允许的最大字符组大小（$2 \le N \le 10^9$，$1 \le L \le 2 \cdot 10^6$，$1 \le K \le L$）。

对于每个测试用例，保证 $\log_2 N$ 要么是一个整数，要么与任何分母不超过 $K$ 的有理数之差的绝对值至少为 $10^{-13}$。

输出格式

对于每个测试用例，输出单独的一行，包含两个整数：$A$ — 编码后消息的最终长度（以比特为单位），以及 $B$ — 所使用的字符组大小（$1 \le B \le K$）。

在字符组大小 $B$ 不大于 $K$（输入中定义）的前提下，编码后的消息长度 $A$ 必须尽可能短。如果有多个最优解，输出其中任意一个即可。

样例

输入样例 1

3
25 1280000 10
2 1000 1000
3 7 3

输出样例 1

5973338 3
1000 1000
14 1

样例解释

第一个测试用例对应瓦西亚教科书中的例子：消息长度为 $1\,280\,000$ 个字符，字符集包含 25 种字符。在这种情况下，如果字符组大小限制在 10 以内，使用大小为 3 的字符组可以使编码后的消息长度达到最小。由于填充，消息末尾会自动添加一个空格。如果像教科书作者最初设想的那样对每个字符单独编码，则需要 $6\,400\,000$ 比特的信息。