问题 6785 --糖果礼盒

6785: 糖果礼盒★★★

时间限制: 1 Sec  内存限制: 128 MB
提交: 6  解决: 3
[提交][状态][命题人:]

题目描述

糖果盒里有n颗糖果,第i颗糖的种类为ai(1ain)

明明的生日马上就要到了,为此你必须按照以下规则从这n颗糖果中挑选一些糖果作为一份生日礼物送给明明:礼物中每种糖果的数量应该是不同的。

例如,假如礼物中有两颗种类1的糖果和两颗种类2的糖果,则是不可行的。假如礼物中有两颗种类1的糖果和一颗种类2的糖果,则是可行的。

为了能够为明明准备生日礼物,相同种类的糖果可以不用全部放入礼盒中,也不是所有种类的糖果都需要放入礼盒中。

请问,礼盒中最多有多少颗糖果呢?

输入

第一行一个整数t(1 ≤ t≤ 2e5):测试样例数;

每个测试样例2行:

第一行一个整数n (1≤n≤2e5):糖果的数量;

第二行共n个整数a1,a2,,an(1ain)ai为第i颗糖果的种类;

输出

      输出共t行,每个测试用例一行一个整数:为礼盒中的最大糖果数量。
样例输入
Copy
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
样例输出
Copy
3
10
9

提示

对于第1个测试样例,我们可以选择2颗种类8的糖果和1颗种类5的糖果放入礼盒中,没有比它更优的方案了。所以礼盒中最多有3颗糖果。

对于第2个测试样例,我们可以选择4颗种类4的糖果,3颗种类2的糖果,2颗种类3的糖果,1颗种类1的糖果,礼盒中最多有10颗糖果。

来源

[提交][状态]