题目描述

光头强有一个由 $n$ 个整数组成的数组 $a$。每次操作需要选择两个不同的索引 $i$ 和 $j$，并从数组中删除 $a_i$ 和 $a_j$。

例如，对于数组 $[2,3,4,2,5]$，光头强可以选择删除索引 $1$ 和 $3$。此操作后，数组变为 $[3,2,5]$。请注意，在任何操作之后，数组的长度都会减少二。

在进行了一系列操作之后，光头强拥有了一个只有不同元素的数组。此外，他还应当确保在操作完成后的数组尽可能长。

更公式地说，光头强完成其操作后的数组遵循以下标准：

• 对任意 $(i \neq j)$ 有 $a_i \neq a_j$ 。
• $a$ 的长度最大化。

输出最终数组的长度。

输入格式

第一行包含单个整数 $t(1≤t≤10^3)$ 表示测试用例数。

每个测试用例的第一行包含一个整数 $n(1≤n≤50)$ 表示数组的长度。

每个测试用例的第二行包含 $n$ 个整数 $a_i(1≤a_i≤10^4)$ 表示数组元素。

输出格式

对于每个测试用例，输出一个整数表示最终数组的长度。

测试样例

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

样例说明

对于第一个测试用例，光头强可以执行以下操作：

选择要删除的索引 $1$ 和 $5$。数组变为 $[2,2,2,3,3,3]→[2,2,3,3]$。

选择要删除的索引 $1$ 和 $4$。数组变为 $[2,2,3,3]→[2,3]$。

最后一个数组的长度为 $2$，因此答案为 $2$。可以证明光头强无法获得更长长度的数组。

对于第二个测试用例，光头强可以执行如下操作：

选择要删除的索引 $3$ 和 $4$。数组变为 $[9,1,9,9,1]→[9,1,1]$。

选择要删除的索引 $1$ 和 $3$。数组变为 $[9,1,1]→[1]$。

最后一个数组的长度为 $1$，因此答案为 $1$。可以证明光头强无法获得更长长度的数组。