为了帮助您为即将到来的 Codeforces 竞赛做好准备,Citlili 设置了一个网格问题,并尝试通过您的输入流为您提供 $$$n$$$ by $$$m$$$ 网格。具体来说,您的输入流应包含以下内容:
- 第一行包含两个整数 $$$n$$$ 和 $$$m$$$ — 网格的尺寸。
- 以下 $$$n$$$ 行每行包含 $$$m$$$ 个整数 — 网格的值。
然而,有人拦截了你的输入流,打乱了所有给定的整数,并将它们全部放在一行上!现在,一行中有$$$k$$$ 个整数,并且你不知道每个整数最初属于哪里。您决定自己确定 $$$n$$$ 和 $$$m$$$ 的值,而不是要求 Citlali 重新发送输入。
输出 Citlali 可能提供的 $$$n$$$ 和 $$$m$$$ 的任何可能值。
输入
第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — 测试用例的数量。
每个测试用例的第一行包含一个整数 $$$k$$$ ($$$3 \leq k \leq 2 \cdot 10^5$$$) — 输入流中的输入总数。
每个测试用例的以下行包含 $$$k$$$ 整数 $$$a_1, a_2, \ldots, a_k$$$ ($$$1 \leq a_i \leq k$$$) — 输入流的打乱输入。保证 $$$n$$$ 和 $$$m$$$ 包含在 $$$k$$$ 整数内。
保证所有测试用例的 $$$k$$$ 总和不超过 $$$2 \cdot 10^5$$$。
输出
对于每个测试用例,输出两个整数,一个可能的值 $$$n$$$ 和 $$$m$$$。如果存在多个可能的答案,则输出任何一个。
示例
输入 #1
5 3 1 1 2 11 3 3 4 5 6 7 8 9 9 10 11 8 8 4 8 3 8 2 8 1 6 2 1 4 5 3 3 8 1 2 6 3 8 5 5 3
输出 #1
1 1 3 3 2 3 4 1 1 6
注意
在第一个测试用例中,初始输入可能如下:
1 1
2
在第二个测试用例中,初始输入可能如下:
3 3
4 5 6
7 8 9
9 10 11