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 Boost ios_base :: sync_with_stdio (0) ; cin.tie(0) ; cout.tie(0) ;

#define  int  long long
#define  ld   long double

#define  pb   push_back
#define  pf   push_front

#define  mp   make_pair
#define  F    first
#define  S    second

#define  deb(x)        cout << #x << x << endl ;
#define  debb(x,y)     cout << #x << x << #y << y << endl ;
#define  debbb(x,y,z)  cout << #x << x << #y <<  y << #z << z << endl ;

#define  all(v)        v.begin(),v.end()
#define  sortall(v)    sort(all(v))

#define  fs(x)         fixed << setprecision(x)

#define  setbits(x)    __builtin_popcount(x)
#define  zrbits(x)     __builtin_ctzll(x)

const int     plus   =  INT32_MAX               ;
const int     minus  =  INT32_MIN               ;
const int     pplus  =  INT64_MAX               ;
const int     mminus =  INT64_MIN               ;
const double  pi     =  3.141592653589793238    ;
const int     mod    =  100000007               ;  //1e9+7

void Go () {
    int n = 0 ;
    cin >> n ;
    map <int,int> m ;
    int dif = 0 ;

    for ( int i = 0 ; i < n ; i++ ) {
        int x = 0 ; cin >> x ;
        m[x]++ ;
    }

    if ( m.size() == 1 ) {
        cout << m.begin()->second << "\n" ;
        return ;
    }
    
    int mp = n/2 ;
    for ( auto i : m ) {
        if ( i.second > mp ) {
            dif += (i.second-mp) ;
        }
    }

    if ( n % 2 ) {
        if ( m.size() > n/2 ) {
            cout << "1\n" ;
        }
        else {
            dif = (2*dif)-1 ;
            cout << max((int)1,dif) << "\n" ;
        }
    }
    else {
        cout << 2*dif << "\n" ;
    }
}


int32_t main () {
    Boost 

    int t = 1 ;
    cin >> t ;
    while ( t-- ) {
        Go() ;
    }
   return 0 ;
}