B. 游戏与彩色弹珠
时间限制：2 秒
内存限制：512 MB

爱丽丝和鲍勃在玩一个游戏。一共有 $n$ 个弹珠，第 $i$ 个弹珠的颜色为 $c_i$。两人轮流行动，爱丽丝先手，然后是鲍勃，再是爱丽丝，依此类推。

轮到某位玩家时，他/她必须从剩下的弹珠中拿走一颗并将其移出游戏。当没有弹珠剩下（即所有 $n$ 个弹珠均被取走）时，游戏结束。

游戏结束时，爱丽丝的得分计算方式如下：

• 对于每种颜色 $x$，如果爱丽丝至少取走了一个该颜色的弹珠，则获得 $1$ 分；
• 额外再获得 $1$ 分（仅对游戏中原有的颜色）——如果爱丽丝取走了该颜色的所有弹珠。

举例：假设有 $5$ 个弹珠，颜色为 $[1,3,1,3,4]$，游戏过程如下：
爱丽丝取第 $1$ 个弹珠（颜色 $1$），鲍勃取第 $3$ 个弹珠（颜色 $1$），爱丽丝取第 $5$ 个弹珠（颜色 $4$），鲍勃取第 $2$ 个弹珠（颜色 $3$），最后爱丽丝取第 $4$ 个弹珠（颜色 $3$）。
那么爱丽丝得分为 $4$：

• $3$ 分来自她至少取过 $1$ 次颜色的弹珠（颜色 $1,3,4$）；
• $1$ 分来自她取走了颜色 $4$ 的所有弹珠。
  注意：上述策略不一定是双方的最优策略。

目标：
爱丽丝希望最大化自己的最终得分，鲍勃希望最小化爱丽丝的最终得分。双方均采取最优策略。

请计算在最优玩法下爱丽丝的得分。

输入
第一行一个整数 $t$（$1 \le t \le 1000$）——测试用例个数。

每个测试用例包含两行：

• 第一行一个整数 $n$（$1 \le n \le 1000$）——弹珠个数；
• 第二行 $n$ 个整数 $c_1, c_2, \dots, c_n$（$1 \le c_i \le n$）——弹珠的颜色。

额外限制：所有测试用例的 $n$ 之和不超过 $1000$。

输出
对于每个测试用例，输出一个整数——在双方最优策略下爱丽丝的得分。

样例
输入

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

输出

4
4
1

样例说明
第二个测试用例中，所有弹珠颜色互不相同，因此无论双方如何行动，爱丽丝的得分始终为 $4$ 分：她获得了两种颜色的所有弹珠（各 $1$ 分额外奖励），但第三种颜色她没有拿到任何弹珠（不得 $1$ 分的基础分）。

第三个测试用例中，所有弹珠颜色相同，因此无论双方如何行动，爱丽丝的得分始终为 $1$ 分：她至少拿到一个该颜色弹珠（得 $1$ 分基础分），但没有拿完所有该颜色弹珠（不得额外 $1$ 分）。