Epic Transformation（思维）

You 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 ai and aj;

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?

Input

The first line contains a single integer t (1≤t≤104). Then t test cases follow.

The first line of each test case contains a single integer n (1≤n≤2⋅105) is length of the array a.

The second line of each test case contains n integers a1,a2,…,an (1≤ai≤109).

It is guaranteed that the sum of n over all test cases does not exceed 2⋅105.

Output

For each test case, output the minimum possible size of the array after applying some sequence of operations to it.

Example Input

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

2

1

题意：在数组中选择两个不同的数字，然后移除，直到不能选择，看看数组中剩下多少个数，数组可以为空。

1、只有一种数字，答案为该数字数量。

2、两种数字，答案为大的数量减去小的数量。

3、三种数字，假设数量从小到大排序 s1 s2 s3 ,可以知道当s1+s2<=s3, 答案为s3-(s1+s2)。

4、当 s1+s2>s3 ,如果(s1+s2+s3)%2 == 0,答案为0，

5、(s1+s2+s3)%2 == 1，答案为1。然后对于数字种数为3个以上的情况，其实都可以转化为3个的情况。

AC代码：

#include<stdio.h>
#include<string.h>
#include<math.h>
#include<stdlib.h>
#include<queue>
#include<stack>
#include<algorithm>
using namespace std;
typedef long long ll;
const int maxn=2*1e5+10;
ll a[maxn];
int main()
{
	ll t,n,i;
	scanf("%d",&t);
	while(t--)
	{
		scanf("%lld",&n);
		for(i=0; i<n; i++)
			scanf("%lld",&a[i]);
		sort(a,a+n);
		ll k=1,maxx=0;
		for(i=1; i<n; i++)
		{
			if(a[i]==a[i-1])
				k++;
			else
			{
				maxx=max(k,maxx);
				k=1;
			}
		}
		maxx=max(k,maxx);//求最多元素的个数
		k=maxx-(n-maxx);
		if(k<0&&n%2==0)
			k=0;
		else if(k<0&&n%2!=0)
			k=1;
		printf("%lld\n",k);
	}
	return 0;
}