题目描述

Alice 和 Bob 在玩一个游戏。一共有 $n$ 个石子，第 $i$ 个的颜色为 $c_i$。Alice 先手，两人轮流取走一颗石子，直到游戏结束。

Alice 的最终分数计算如下：

• 对于每一个颜色 $x$，如果 Alice 有至少一颗该颜色的石子，她获得 $1$ 分。
• 对于每一个颜色 $x$，如果她拥有全部该颜色的石子，她额外获得 $1$ 分（只考虑游戏中出现的颜色）。

比如，假设有颜色为 $[1,3,1,3,4]$ 的五颗石子，Alice 第一次拿第 $1$ 颗，Bob 拿第 $3$ 颗，然后 Alice 拿第 $5$ 颗，Bob 拿第 $2$ 颗，最后 Alice 拿第 $4$ 颗。最终，Alice 获得 $4$ 分：$3$ 分来自拿走至少一颗颜色为 $1,3,4$ 的石子，剩下 $1$ 分来自拿走全部颜色为 $4$ 的石子。注意这一方案不一定是对双方最优的。

Alice 想最大化她的分数，而 Bob 想最小化这个分数，假设两人都足够聪明。求 Alice 的最终得分。

输入格式

第一行，一个整数 $t$ ($1\le t \le 1000$)，表示数据组数。

对于每组数据，输入两行：

• 第一行，一个整数 $n$ ($1\le n\le 1000$)，表示石子个数。
• 第二行，$n$ 个整数 $c_1,c_2,\cdots,c_n$ ($1\le c_i\le n$)，表示石子的颜色。

保证所有 $n$ 之和不超过 $1000$。

输出格式

对于每组数据，输出一行，一个整数，表示 Alice 的最终分数。

翻译：HYdroKomide

样例

3
5
1 3 1 3 4
3
1 2 3
4
4 4 4 4

4
4
1