UOJ Logo

NOI.AC

1S 512MB

#1578. 六花的礼品

Statistics

题目描述

六花有$n$个礼品盒,每个礼品盒中装着一个小礼物,可能有些礼品盒中的礼物是重复的,第$i$个礼品盒中的礼物的种类是$A_{i}$。 六花想要从这些礼物中取一些出来送给勇太,但是她不想送出数量重复的,属于不同种类的礼物,同时她还想要送出的礼物总数量尽可能多。 请你帮助她做出最佳的选择,挑选出尽量多的符合条件的礼物。

输入格式

第一行一个整数$T$,表示数据组数 对于每组数据: 第一行一个数字$n$,表示有$n$ < 1e6 个礼品盒 第二行有$n$个数为$A_{i} \le 1e6$,

输出格式

输出$T$行,每行一个整数表示答案

样例数据

input

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

output

3
10
9

对于样例一: 可以取一个1或者3或者5或者6,再取两个4或者8共3个。

数据规模与约定

对于40%的数据,$n\le 10$ 对于100%的数据,$n\le 100000$ 对于所有数据,$T\le 10$