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$$$) — 数组的元素。
输出
对于每个测试用例,输出一个整数 - 最终数组的长度。请记住,在最终数组中,所有元素都是不同的,并且其长度是最大的。
示例
输入 #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
输出 #1
2 1 2 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]$$$。
对于第二个测试用例 Sho 可以执行如下操作:
1. 选择要删除的索引 $$$3$$$ 和 $$$4$$$。该数组变为 $$$[9, 1, 9, 9, 1] \rightarrow [9, 1, 1]$$$。
2. 选择要删除的索引 $$$1$$$ 和 $$$3$$$。该数组变为 $$$[9, 1, 1] \rightarrow [1]$$$。