问题 D: 删除元素

题目描述

小Y有一个由n个整数组成的数组a。一个操作定义为：选择两个不同的索引i和j，从数组中移除ai和aj。

例如，对于数组[2,3,4,2,5]，小Y可以选择删除索引1和3。在这个操作之后，数组变成了[3,2,5]。请注意，在每个操作完成后，数组的长度都会减少2。 在他进行了一些操作之后，小Y的数组中所有数都各不相同。此外，还要求所得到的数组是最长的。

更格式化地说，在小Y进行了操作之后，数组遵守了这些标准：

不存在ai=aj(i<j)这样的对；

a的长度是最大的。

输入

第一行包含一个整数t（1≤t≤103）--测试案例的数量。

每个测试案例的第一行包含一个整数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

提示

【样例解释】

对于第一个测试案例，小Y可以进行如下操作： 选择索引1和5来删除。数组变成[2,2,2,3,3,3]→[2,2,3,3]。 选择索引1和4来删除。数组变成[2,2,3,3]→[2,3]。 最后的数组长度为2，所以答案是2。可以证明小Y不能得到一个长度更长的数组。

对于第二个测试案例，小Y可以进行如下的操作： 选择索引3和4进行删除。数组变成[9,1,9,9,1]→[9,1,1]。

选择索引1和3来删除。数组变成[9,1,1]→[1]。 最后的数组长度为1，所以答案是1。可以证明小Y不能得到一个更长的数组。

【数据规模】

30%的数据，t≤5，n≤10；

其中10%的数据，所有数都相同；

100%的数据，1≤t≤103，1≤n≤50，1≤ai≤104。

求大佬代码，在线等，谢谢！！！