← 返回题目列表

Codeforces · 1692/B

B. 全部不同

中文机器翻译题面 查看原题

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]$$$。