CF2042B Game with Colored Marbles

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](https://www.luogu.com.cn/user/299883)

In the second test case of the example, the colors of all marbles are distinct, so, no matter how the players act, Alice receives $ 4 $ points for having all marbles of two colors, and no marbles of the third color. In the third test case of the example, the colors of all marbles are the same, so, no matter how the players act, Alice receives $ 1 $ point for having at least one (but not all) marble of color $ 4 $ .