CF1692B.All Distinct

Sho has an array $a$ consisting of $n$ integers. An operation consists of choosing two distinct indices $i$ and $j$ and removing $a_i$ and $a_j$ from the array.

For example, for the array $[2, 3, 4, 2, 5]$, Sho can choose to remove indices $1$ and $3$. After this operation, the array becomes $[3, 2, 5]$. Note that after any operation, the length of the array is reduced by two.

After he made some operations, Sho has an array that has only distinct elements. In addition, he made operations such that the resulting array is the longest possible.

More formally, the array after Sho has made his operations respects these criteria:

• No pairs such that ($i \lt j$) and $a_i = a_j$ exist.
• The length of $a$ is maximized.

Output the length of the final array.

Sho 有一个由 $n$ 个整数组成的数组 $a$。一次操作是指选择两个不同的下标 $i$ 和 $j$，并从数组中移除 $a_i$ 和 $a_j$。

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

在执行若干次操作后，Sho 得到了一个所有元素互不相同的数组。此外，他所执行的操作使得最终数组的长度尽可能长。

更准确地说，Sho 执行完所有操作后的数组需满足以下条件：

• 不存在下标对 $(i, j)$ 满足 $i \lt j$ 且 $a_i = a_j$（即数组中无重复元素）；
• 数组的长度达到最大可能值。

请输出最终数组的长度。

The first line contains a single integer $t$ ($1 \leq t \leq 10^3$) — the number of test cases.

The first line of each test case contains a single integer $n$ ($1 \leq n \leq 50$) — the length of the array.

The second line of each test case contains $n$ integers $a_i$ ($1 \leq a_i \leq 10^4$) — the elements of the array.

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

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

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

For each test case, output a single integer — the length of the final array. Remember that in the final array, all elements are different, and its length is maximum.

对于每个测试用例，输出一个整数——即最终数组的长度。注意：在最终数组中，所有元素互不相同，且其长度达到最大。

For the first test case Sho can perform operations as follows:

1. Choose indices $1$ and $5$ to remove. The array becomes $[2, 2, 2, 3, 3, 3] \rightarrow [2, 2, 3, 3]$.
2. Choose indices $1$ and $4$ to remove. The array becomes $[2, 2, 3, 3] \rightarrow [2, 3]$.

The final array has a length of $2$, so the answer is $2$. It can be proven that Sho cannot obtain an array with a longer length.

For the second test case Sho can perform operations as follows:

1. Choose indices $3$ and $4$ to remove. The array becomes $[9, 1, 9, 9, 1] \rightarrow [9, 1, 1]$.
2. Choose indices $1$ and $3$ to remove. The array becomes $[9, 1, 1] \rightarrow [1]$.

The final array has a length of $1$, so the answer is $1$. It can be proven that Sho cannot obtain an array with a longer length.

对于第一个测试用例，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 无法得到更长的数组。