给定一个数组 $$$a$$$,长度为 $$$n$$$,由整数组成。您可以对数组 $$$a$$$ 应用以下由多个步骤组成的操作零次或多次:
- 在数组 $$$a_i$$$ 和 $$$a_j$$$ 中选择两个不同的数字;
- 从数组中删除第 $$$i$$$ 和第 $$$j$$$ 个元素。
例如,如果 $$$n=6$$$ 且 $$$a=[1, 6, 1, 1, 4, 4]$$$,则可以执行以下操作序列:
- 选择$$$i=1,j=5$$$。数组 $$$a$$$ 等于 $$$[6, 1, 1, 4]$$$;
- 选择$$$i=1,j=2$$$。数组 $$$a$$$ 等于 $$$[1, 4]$$$。
对数组应用一些操作序列后,数组的最小大小是多少?
输入
第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$)。然后是 $$$t$$$ 测试用例。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) 是数组 $$$a$$$ 的长度。
每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^9$$$)。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。
输出
对于每个测试用例,在对其应用一些操作序列后输出数组的最小可能大小。
示例
输入 #1
5 6 1 6 1 1 4 4 2 1 2 2 1 1 5 4 5 4 5 4 6 2 3 2 1 3 1
输出 #1
0 0 2 1 0