您控制着 $$$n$$$ 名学生,并且您必须恰好组成两个由部分学生组成的团队。每个学生都有自己的技能,第 $$$i$$$ 个学生技能用整数 $$$a_i$$$ 表示(不同的学生可以拥有相同的技能)。
那么,关于团队。首先,这两支球队的规模应该相同。还有两个限制:
- 第一队应由具有独特技能的学生组成(即第一队中的所有技能都是独一无二的)。
- 第二队应由具有相同技能的学生组成(即第二队中的所有技能都是平等的)。
请注意,第一队的某些学生与第二队的学生具有相同的技能是允许的。
考虑一些例子(给出了技能):
- $$$[1, 2, 3]$$$, $$$[4, 4]$$$ 不是一对好的球队,因为尺寸应该相同;
- $$$[1, 1, 2]$$$, $$$[3, 3, 3]$$$ 不是一对好队伍,因为第一队不应包含具有相同技能的学生;
- $$$[1, 2, 3]$$$, $$$[3, 4, 4]$$$ 不是一对好的团队,因为第二个团队应该包含具有相同技能的学生;
- $$$[1, 2, 3]$$$, $$$[3, 3, 3]$$$ 是一对很好的队伍;
- $$$[5]$$$、$$$[6]$$$ 是一对很好的团队。
你的任务是找到可以组成一对有效团队的最大可能规模 $$$x$$$,其中每个团队的规模为 $$$x$$$ (第一团队中的技能需要是唯一的,第二团队中的技能应该是相同的)。一名学生不能属于多个团队。
您必须回答 $$$t$$$ 独立测试用例。
输入
输入的第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。然后是 $$$t$$$ 测试用例。
测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — 学生人数。测试用例的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le n$$$),其中 $$$a_i$$$ 是第 $$$i$$$ 个学生的技能。不同的学生可以拥有相同的技能。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$ ($$$\sum n \le 2 \cdot 10^5$$$)。
输出
对于每个测试用例,打印答案 - 可以组成一对有效团队的最大可能规模 $$$x$$$,其中每个团队规模为 $$$x$$$。
示例
输入 #1
4 7 4 2 4 1 4 3 4 5 2 1 5 4 3 1 1 4 1 1 1 3
输出 #1
3 1 0 2
注意
在示例的第一个测试用例中,可以构建两个规模为 $$$3$$$ 的团队:第一个团队是 $$$[1, 2, 4]$$$,第二个团队是 $$$[4, 4, 4]$$$。请注意,还有一些其他方法可以构建两个规模为 $$$3$$$ 的有效团队。