D. Epic Transformationtime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard outputYou are given an array a of length n consisting of integers. You can apply the following operation, consisting of several steps, on the array a zero or more times:   you select two different numbers in the array a_i and a_j;  you remove i-th and j-th elements from the array. For example, if n=6 and a=[1, 6, 1, 1, 4, 4], then you can perform the following sequence of operations:   select i=1, j=5. The array a becomes equal to [6, 1, 1, 4];  select i=1, j=2. The array a becomes equal to [1, 4]. What can be the minimum size of the array after applying some sequence of operations to it?InputThe first line contains a single integer t (1 \le t \le 10^4). Then t test cases follow.The first line of each test case contains a single integer n (1 \le n \le 2 \cdot 10^5) is length of the array a.The second line of each test case contains n integers a_1, a_2, \ldots, a_n (1 \le a_i \le 10^9).It is guaranteed that the sum of n over all test cases does not exceed 2 \cdot 10^5.OutputFor each test case, output the minimum possible size of the array after applying some sequence of operations to it.ExampleInput
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
Output
0
0
2
1
0

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

0 0 2 1 0 
['constructive algorithms', 'data structures', 'greedy', '*1400']