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;
 
typedef long long ll;
typedef long double ld;
 
typedef pair<ll, ll> pll;
typedef pair<ld, ld> pld;
typedef pair<string, string> pss;
 
typedef vector<ll> vll;
typedef vector<ld> vld;
typedef vector<pll> vpll;
typedef vector<pld> vpld;
typedef vector<vll> vvll;
 
typedef queue<ll> qll;
typedef queue<ld> qld;
typedef queue<vll> qvll;
typedef queue<vld> qvld;
typedef queue<pll> qpll;
typedef queue<pld> qpld;
 
#define unomi unordered_map<int, int>
#define omi map<int, int>
 
#define endl "\n"
#define mp make_pair
#define pb push_back
#define all(v) v.begin(), v.end()
#define fi first
#define se second
#define lb lower_bound
#define ub upper_bound
#define pi 3.14159265358979323846
#define MAX 1e18
#define ms(s, n) memset(s, n, sizeof(s))
#define prec(n) fixed << setprecision(n)
 
#define fori(p, n) for (ll i = p; i < (ll)n; i++)
#define forj(p, n) for (ll j = p; j < (ll)n; j++)
#define fork(p, n) for (ll k = p; k < (ll)n; k++)
#define foriv(p, n, v) for (ll i = p; i < (ll)n; i += v)
#define forjv(p, n, v) for (ll j = p; j < (ll)n; j += v)
#define forkv(p, n, v) for (ll k = p; k < (ll)n; k += v)
 
#define rfori(a, b) for(ll i = a; i>= b; i--)
#define rall(x) x.rbegin(), x.rend()
 
#define mod 1000000007
 
inline ll modnum(ll a) { return (a + mod) % mod; }
inline ll modadd(ll a, ll b) { return ((a % mod) + (b % mod)) % mod; } //a+b
inline ll modsub(ll a, ll b) { return ((a % mod) - (b % mod)) % mod; } //a-b
inline ll modmul(ll a, ll b) { return ((a % mod) * (b % mod)) % mod; } //a*b
inline ll modexp(ll a, ll b) { return ((a % mod) ^ b) % mod; }         //a^b
 
#define bolt                          \
    ios_base::sync_with_stdio(false); \
    cin.tie(0);                       \
    cout.tie(0);
#define setbits(a) __builtin_popcountll(a)
#define start \
    ll t;     \
    cin >> t; \
    while (t--)
 
template <typename T>
istream &operator>>(istream &input, vector<T> &data) {
	for (T &x : data) input >> x;
	return input;
}
template <typename T>
ostream &operator<<(ostream &output, const vector<T> &data) {
	for (const T &x : data) output << x << " ";
	return output;
}
template <typename T>
ostream &operator<<(ostream &output, const set<T> &data) {
	for (auto it : data) output << it << " ";
	return output;
}
template <typename T>
ostream &operator<<(ostream &output, const unordered_set<T> &data) {
	for (auto it : data) output << it << " ";
	return output;
}
template <typename T, typename S>
ostream &operator<<(ostream &output, const map<T, S> &data) {
	for (auto it : data) output << it.first << " " << it.second << endl;
	return output;
}
template <typename T, typename S>
ostream &operator<<(ostream &output, const unordered_map<T, S> &data) {
	for (auto it : data) output << it.first << " " << it.second << endl;
	return output;
}
template <typename T, typename S>
ostream &operator<<(ostream &output, const pair<T, S> &data) {
	output << data.first << " " << data.second << endl;
	return output;
}
 
void IO() {
#ifndef ONLINE_JUDGE
	freopen("input1.txt", "r", stdin);
	freopen("output1.txt", "w", stdout);
#endif
}
 
inline ll fact(ll n) {
	if (n <= 1) return 1;
	return n * fact(n - 1);
}
inline ll nCr(ll n, ll r) {
	ll res = 1;
	if (r > n - r)
		r = n - r;
	for (ll i = 0; i < r; i++)
	{
		res *= n - i;
		res /= i + 1;
	}
	return res;
}
inline ll nPr(ll n, ll r) { return fact(n) / fact(n - r); }
 
void swap(ll& a, ll& b) {
	ll tmp;
	if (a < b) {
		tmp = a;
		a = b;
		b = tmp;
	}
}
 
inline ll gcd(ll a, ll b) {
	if (b == 0) return a;
	if (a < b) swap(a, b);
	return gcd(b, a % b);
}
inline ll lcm(ll a, ll b) { return (a / gcd(a, b) * b); }
inline ll ceil(ll num, ll den) { return ((num + den - 1) / den); }
inline bool sortbysec(const pair<ll, ll> &a, const pair<ll, ll> &b) { return (a.second < b.second); }
 
inline ll pw(ll x, ll y) {
	ll res = 1;
	x = x % mod;
	while (y > 0) {
		if (y & 1) res = (1ll * res * x) % mod;
		y = y >> 1;
		x = (1ll * x * x) % mod;
	}
	return res;
}
 
// nCr & nPr with mod
// nCr = fact(n) / (fact(r) x fact(n - r))
// nCr % p = (fac[n] * modInverse(fac[r]) % p * modInverse(fac[n - r]) % p) % p;
const int N = 1e5;
int fac[N], ifac[N], inv[N];
void precalc_factorial() {
	fac[0] = ifac[0] = fac[1] = ifac[1] = inv[0] = inv[1] = 1;
	for (int i = 2; i < N; i++) {
		fac[i] = 1LL * fac[i - 1] * i % mod;
		inv[i] = mod - 1LL * inv[mod % i] * (mod / i) % mod;
		ifac[i] = 1LL * ifac[i - 1] * inv[i] % mod;
	}
}
inline int ncr(int n, int r) {
	if (r < 0 | r > n) return 0;
 
	return 1LL * fac[n] * ifac[r] % mod * ifac[n - r] % mod;
}
inline int npr(int n, int r) {
	if (r < 0 | r > n) return 0;
 
	return 1LL * fac[n] * ifac[n - r] % mod;
}
 
struct node {
	ll val;
	node *left;
	node *right;
	node(ll x) : val(x), left(NULL), right(NULL) {}
	// vector<TreeNode *> children;
	// TreeNode(ll x) : val(x) {}
};
 
void next_greater(vll &v, vll &res)
{
	if (v.empty())
		return;
	stack<pll> stk;
	for (int i = 0; i < v.size(); i++) {
		while (!stk.empty() && stk.top().first <= v[i]) {
			res[stk.top().second] = v[i];
			stk.pop();
		}
		stk.push({v[i], i});
	}
}
 
set<ll> primes;
void sieve(ll n) {
	vll arr(n + 1, 1);
 
	for (ll p = 2; p * p <= n; p++) {
		if (arr[p]) {
			for (ll i = p * p; i <= n; i += p) arr[i] = 0;
		}
	}
	if (!primes.empty()) primes.clear();
	for (ll p = 2; p <= n; p++) if (arr[p]) primes.insert(p);
}
 
inline bool is_prime(ll n) {
	for (ll i = 2; i <= sqrt(n); i++) {
		if (n % i == 0) return false;
	}
	return true;
}
 
//void tin(vll& a){ ll n = a.size(); fori(0, n) cin>>a[i];}
//void pot(vll& a){ ll n = a.size(); fori(0, n) cout<<a[i]<<" "; cout<<endl;}
//void spot(string& s){ ll n = s.size(); fori(0, n)cout<<s[i]; cout<<endl;}
 
/*void solve() {
 
}*/

int main() {
	bolt;
	IO();
	//precalc_factorial();
	//sieve(100);
	start{
	  ll n, max_cnt = INT_MIN;
	  cin>>n;
	  vll arr(n);
	  cin>>arr;
	  map<ll,ll> mp;
	  fori(0, n){
	      mp[arr[i]]++;
	      if(max_cnt < mp[arr[i]]) max_cnt = mp[arr[i]];
	  }
	  
	  ll same = max_cnt;
	  ll diff = n - same;
	  if(same <= diff){
	      if(n&1) cout<<1<<endl;
	      else cout<<0<<endl;
	  }
	  else cout<<same-diff<<endl;
	}
	return 0;
}