题目描述

Sho 有一个包含 $n$ 个整数的数组 $a$。每次操作可以选择两个不同的下标 $i$ 和 $j$，并从数组中移除 $a_i$ 和 $a_j$。

例如，对于数组 $[2, 3, 4, 2, 5]$，Sho 可以选择移除下标 $1$ 和 $3$，操作后数组变为 $[3, 2, 5]$。注意，每次操作后，数组长度减少 $2$。

经过若干次操作后，Sho 得到的数组中所有元素都互不相同。此外，他进行操作的方式使得最终数组的长度尽可能大。

更正式地说，Sho 操作后的数组满足以下条件：

• 不存在一对下标 $(i < j)$ 使得 $a_i = a_j$。
• 数组 $a$ 的长度最大。

请输出最终数组的长度。

输入格式

第一行包含一个整数 $t$（$1 \leq t \leq 10^3$），表示测试用例的数量。

每个测试用例的第一行包含一个整数 $n$（$1 \leq n \leq 50$），表示数组的长度。

每个测试用例的第二行包含 $n$ 个整数 $a_i$（$1 \leq a_i \leq 10^4$），表示数组的元素。

输出格式

对于每个测试用例，输出一个整数，表示最终数组的长度。注意，最终数组中所有元素都不同，并且长度最大。

说明/提示

对于第一个测试用例，Sho 可以按如下方式进行操作：

1. 选择下标 $1$ 和 $5$ 移除。数组变为 $[2, 2, 2, 3, 3, 3] \rightarrow [2, 2, 3, 3]$。
2. 选择下标 $1$ 和 $4$ 移除。数组变为 $[2, 2, 3, 3] \rightarrow [2, 3]$。

最终数组长度为 $2$，因此答案为 $2$。可以证明 Sho 无法得到更长的数组。

对于第二个测试用例，Sho 可以按如下方式进行操作：

1. 选择下标 $3$ 和 $4$ 移除。数组变为 $[9, 1, 9, 9, 1] \rightarrow [9, 1, 1]$。
2. 选择下标 $1$ 和 $3$ 移除。数组变为 $[9, 1, 1] \rightarrow [1]$。

最终数组长度为 $1$，因此答案为 $1$。可以证明 Sho 无法得到更长的数组。

由 ChatGPT 4.1 翻译

样例

4
6
2 2 2 3 3 3
5
9 1 9 9 1
4
15 16 16 15
4
10 100 1000 10000

2
1
2
4