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
import java.util.*;
import java.math.*;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;


public class b{ 

     static FastScanner sc;
     static long[] arr;
     static long mul,mul1;
     static int[] spf;
     static int n,q;
     static long mod = ((long)(1e9))+7;

     static long[] st;
    static long[] lazy;

    static void func(int n) {
        st = new long[5 * n];
        lazy = new long[5 * n];
        for (int i = 0; i < 5* n; i++) {
            st[i] = 1;
            lazy[i] = 1;
        }
    }

    static void pushdown(int node, int ss, int se) {
        st[node] *= lazy[node];
        if (ss != se) {
            lazy[2 * node + 1] *= lazy[node];
            lazy[2 * node + 2] *= lazy[node];
        }
        lazy[node] = 1;

    }

    static void update(int node, int ss, int se, int l, int r, int val) {
        pushdown(node, ss, se);
        // break condition
        if (se < l || ss > r) {
            return;
        }
        // tag condition
        if (ss >= l && se <= r) {
            lazy[node] = mod(lazy[node]*val,mod);
            pushdown(node, ss, se);
            return;
        }
        int mid = (ss + se) / 2;
        update(2 * node + 1, ss, mid, l, r, val);
        update(2 * node + 2, mid+1, se, l, r, val);
        st[node] = combine(st[2 * node + 1], st[2 * node + 2]);
    }

    static long combine(long a, long b) {
        if (b == 0) {
            return a;
        }
        return combine(b, a % b);
    }

    static long get(int node, int ss, int se, int l, int r) {
        pushdown(node, ss, se);
        if (se < l || ss > r) {
            return 1;
        }
        if (ss >= l && se <= r) {

            return st[node];
        }
        int mid = (ss + se) / 2;
        if(mid<l){
            return get(2*node+2, mid+1, se, l, r);
        }else if(mid+1>r){
            return get(2*node+1, ss, mid, l, r);
        }
        return combine(get(2 * node + 1, ss, mid, l, r), get(2 * node + 2, mid + 1, se, l, r));
    }

    

    // public static void getFactorization(int x) 
    // { 
    //     // ArrayList<Integer> ret = new ArrayList<Integer>(); 
    //     mul = 1;
    //     mul1 = 1;
    //     int curr = 0;
    //     while (x != 1) 
    //     {      
    //         // System.out.println(spf[x]);
    //         int num = spf[x];
    //         // ret.add(num); 
    //         while(x%num == 0){
    //             x /= num;
    //             curr += 1;
    //         }
    //         if(curr%2 == 0)
    //             mul1 *= num;
    //         else
    //             mul *= num;
    //         curr = 0;
    //     } 
    //     // System.out.println(mul + " " + mul1);
    //     // System.out.println(mul);
    // } 

     public static void solve(){

        PriorityQueue<Integer> pq = new PriorityQueue<>(10,Collections.reverseOrder());
        ruffleSort(arr);
        for(int i = 0 ; i < n; ){

            long num = arr[i];
            int count = 0;

            while(i < n  && arr[i] == num){
                count += 1;
                i += 1;
            }

            pq.add(count);
        }

        int prev = -1;
        while(!pq.isEmpty()){
            Integer node1 = pq.poll();
            if(pq.isEmpty()){
                if(prev != -1)
                    System.out.println(Math.abs(node1-prev));
                else{
                    System.out.println(node1);
                }
                return;
            }
            Integer node2 = pq.poll();

            if(node2 == node1 && node1 == 1){
                if(prev != -1){
                    pq.add(prev);
                    prev = -1;
                }
                continue;
            }
            node1 -= 1;
            node2 -= 1;
            if(prev != -1){
                pq.add(prev);
                prev = -1;
            }
            if(node2 != 0)
                prev = node2;
            if(node1 != 0)
                pq.add(node1);
        }

        System.out.println(0);


     }

        
     public static void main(String[] args) {

            sc = new FastScanner();
            // Scanner sc = new Scanner(System.in);
            int t = sc.nextInt();
            // int t = 1;
            while(t > 0){

                n = sc.nextInt();
                // q = sc.nextInt();
                arr = new long[n];
                for(int i = 0 ; i < n ; i++)
                    arr[i] = sc.nextLong();
                solve();       
                t -= 1;
            }

     }

    // Use this instead of Arrays.sort() on an array of ints. Arrays.sort() is n^2
    // worst case since it uses a version of quicksort. Although this would never
    // actually show up in the real world, in codeforces, people can hack, so
    // this is needed.
    static void ruffleSort(long[] a) {
        //ruffle
        int n=a.length;
        Random r=new Random();
        for (int i=0; i<a.length; i++) {
            int oi=r.nextInt(n);long temp=a[i];
            a[i]=a[oi];
            a[oi]=temp;
        }
        
        //then sort
        Arrays.sort(a);
    }
    public static long gcd(long a, long b)
    {
      if (b == 0)
        return a;
      return gcd(b, a % b); 
    }
    public static long mod(long x, long mod)
{
    long result = x % mod;
    if (result < 0)
    {
        result += mod;
    }
    return result;
}

    static class Node{
            int s;
            int e;
            Node(int f,int s){
                this.s = f;
                this.e = s;
            }
        }
    
    // Use this to input code since it is faster than a Scanner
    static class FastScanner {
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st=new StringTokenizer("");
        String next() {
            while (!st.hasMoreTokens())
                try {
                    st=new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            return st.nextToken();
        }
        
        int nextInt() {
            return Integer.parseInt(next());
        }
        int[] readArray(int n) {
            int[] a=new int[n];
            for (int i=0; i<n; i++) a[i]=nextInt();
            return a;
        }
        long nextLong() {
            return Long.parseLong(next());
        }
    }
}
 