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 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?

Input

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

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

The second line of each test case contains n integers a_1, a_2, …, a_n (1 ≤ a_i ≤ 10^9).

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

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


0
0
2
1
0
#include <bits/stdc++.h>
 
using namespace std;
 
#define endl '\n'
#define ll long long
#define int long long
#define ld  long double
const int32_t INFint = 1e9;
const ll INFll = 1e18;
const ll INF = 9e18;
const ld PI = acos(-1);
#define MOD 1000000007
#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
 
#define vi vector < int >
#define vii vector < vector < int > >
#define pii pair < int , int >
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define foreach(it,v) for( __typeof((v).begin())it = (v).begin() ; it != (v).end() ; it++ )
 
int powersOfTwo[31] = {1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 
131072, 262144, 524288, 1048576, 2097152, 4194304, 8388608, 16777216, 33554432, 67108864, 134217728, 268435456, 536870912, 1073741824};
int power(int x, int y){ int r = 1; while(y>0){ if(y&1) r = r * x; y = y >> 1; x = x * x; } return r; }
ll powerMod(ll x,ll y,ll p ){ll res=1;x%=p;while(y>0){if(y&1)res=(res*x)%p;y=y>>1;x=(x*x)%p;}return res;}
ll gcd(ll a, ll b){if(!b)return a;return gcd(b, a % b);} 
ll lcm(ll a , ll b){return (a*b)/gcd(a,b);}
int log2n(int n){return (n>1) ? 1 + log2n(n/2) : 0;}
int twoPower(int n){return (n) ? 2 * twoPower(n-1) : 1;}
 
#define deb1(x)				cout<<#x<<": "<<x<<endl
#define deb2(x, y)			 cout<<#x<<": "<<x<<" | "<<#y<<": "<<y<<endl
#define deb3(x, y, z)		  cout<<#x<<": " <<x<<" | "<<#y<<": "<<y<<" | "<<#z<<": "<<z<<endl
#define deb4(a, b, c, d)	   cout<<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<endl
#define deb5(a, b, c, d, e)		cout<<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<" | "<<#e<< ": "<<e<<endl
#define deb6(a, b, c, d, e, f) 	 cout<<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<" | "<<#e<< ": "<<e<<" | "<<#f<<": "<<f<<endl
 
#define For(i, a, b) for (ll i = a; i < b; i++)
#define loop(i,a,b) for (int i = a; i < b; i++)
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(),v.rend()
#define gll(a,n) for(ll i=0;i<n;i++) cin>>a[i];
#define gint(a,n) for(int i=0;i<n;i++) cin>>a[i];
#define setZero(a,n) for(int i=0;i<n;i++) a[i]=0;
#define printArray(a,s,e) for(int i=s;i<e;i++) {cout << a[i] << " ";} cout << endl;
#define showArray(a) {int n=a.size(); for(int i=0;i<a.size();i++) {cout << a[i] << " ";} cout << endl;}
#define nl cout << endl
#define printclock cerr<<"Time : "<<1000*(ld)clock()/(ld)CLOCKS_PER_SEC<<"ms\n";
#define fac(a) tgamma(a+1)
//---------------------------------------------------------------------------------------------------------------------------------------
//---------------------------------------------------------------------------------------------------------------------------------------
//--------------------------------------------------------------------------------------------------------------------------------------- 
int32_t main(){fast;
	#ifndef ONLINE_JUDGE
		freopen("input.txt","r",stdin);
		freopen("output.txt","w",stdout);
	#endif
 
	int tt = 1;
	cin >> tt;
	int tc = tt;
	while(tt--){
		int n;
		cin >> n;
		int k = n;
		vi arr(n);
		gint(arr, n);
		map<int, int> m;
		for(int i=0;i<n;i++) m[arr[i]]++;

		vi tr;
		for(auto it: m) tr.pb(it.ss);
		sort(all(tr));
		reverse(all(tr));

		n = tr.size();
		int sum = 0;
		for(int i=1;i<n;i++){
			sum += tr[i];
		}

		if(tr[0] - sum > 0){
			cout << tr[0] - sum << endl;
		}

		else if(k%2) cout << 1 << endl;
		else if(k%2 == 0) cout << 0 << endl;

	}
	printclock;
}
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 