这个问题实际上是同一竞赛中问题 G 的子问题。
糖果盒中有 $$$n$$$ 糖果。第 $$$i$$$ 糖果的类型为 $$$a_i$$$ ($$$1 \le a_i \le n$$$)。
您必须使用其中一些糖果来准备一份礼物,但有以下限制:礼物中每种类型的糖果数量应该完全不同(即,例如,包含两颗 $$$1$$$ 类型的糖果和两颗 $$$2$$$ 类型的糖果的礼物是不好的)。
礼物中可能完全没有多种类型的糖果。也有可能并非所有类型的糖果都会被当作礼物。
你的任务是找出你可以用你拥有的糖果准备的最大可能尺寸的礼物。
您必须回答 $$$q$$$ 独立查询。
如果您是 Python 程序员,请在提交代码时考虑使用 PyPy 而不是 Python。
输入
输入的第一行包含一个整数 $$$q$$$ ($$$1 \le q \le 2 \cdot 10^5$$$) — 查询数。每个查询由两行表示。
每个查询的第一行包含一个整数 $$$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$$$。
输出
对于每个查询,打印一个整数 - 您可以使用在此查询中获得的糖果以及问题陈述中描述的限制组成的单件礼物的最大可能大小。
示例
输入 #1
3 8 1 4 8 4 5 6 3 8 16 2 1 3 3 4 3 4 4 1 3 2 2 2 4 1 1 9 2 2 4 4 4 7 7 7 7
输出 #1
3 10 9
注意
在第一个查询中,您可以准备一份礼物,其中包含两颗 $$$8$$$ 类型的糖果和一颗 $$$5$$$ 类型的糖果,总共 $$$3$$$ 糖果。
请注意,这不是唯一可能的解决方案 - 获取两颗 $$$4$$$ 类型的糖果和一颗 $$$6$$$ 类型的糖果也是有效的。