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
/*
 * To change this license header, choose License Headers in Project Properties.
 * To change this template file, choose Tools | Templates
 * and open the template in the editor.
 */

/**
 *
 * @author wilso
 */
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.*;
public class codeforces {
    static Integer[][] cache;
    public static void main(String[] args) {
        FastScanner sc = new FastScanner();
        PrintWriter pw = new PrintWriter(System.out);

        int tc = sc.ni();
        for (int rep = 0; rep < tc; rep++) {
            int n = sc.ni();
            int[] arr = sc.intArray(n);
            pw.println(solve(arr));
            
        }
        
        
        pw.close();
    }
    static int solve(int[] nums) {
        Map<Integer, Integer> map = new HashMap();
        for (int n : nums) {
            map.put(n, map.getOrDefault(n, 0)+1);
        }
        MultiSet ms = new MultiSet();
        for (int k : map.keySet()) {
            ms.add(map.get(k));
        }
//        System.out.println(ms.map.toString() + " " + ms.size());
        
        while (ms.size() > 1) {
            int x = ms.last();
            ms.remove(x);
            int y = ms.last();
            ms.remove(y);
            
            y--;
            x--;
            if (x > 0) ms.add(x);
            if (y > 0) ms.add(y);
//            System.out.println(ms.map.toString());
//            System.out.println(ms.size());
        }
//        System.out.println();
        int ret = 0;
        while (!ms.isEmpty()) {
            ret += ms.last();
            ms.remove(ms.last());
        }
        return ret;
    }
            
        
       
        
   
    
    
    static long pow(long num, long exp, long mod){
        long ans=1;
        for(int i=1;i<=exp;i++){
            ans=(ans*num)%mod;
        }
        return ans;
    }
    static boolean isPrime(int n)
    {
 
        // Check if number is less than
        // equal to 1
        if (n <= 1)
            return false;
 
        // Check if number is 2
        else if (n == 2)
            return true;
 
        // Check if n is a multiple of 2
        else if (n % 2 == 0)
            return false;
 
        // If not, then just check the odds
        for (int i = 3; i <= Math.sqrt(n); i += 2) 
        {
            if (n % i == 0)
                return false;
        }
        return true;
    }
    static int gcd(int a, int b)
    {
        if (a == 0)
            return b; 
        return gcd(b % a, a); 
    }
     
    // method to return LCM of two numbers
    static int lcm(int a, int b)
    {
        return (a / gcd(a, b)) * b;
    }
    public static void sort(int[] arr) {
        Random rgen = new Random();
        for (int i = 0; i < arr.length; i++) {
            int r = rgen.nextInt(arr.length);
            int temp = arr[i];
            arr[i] = arr[r];
            arr[r] = temp;
        }
        Arrays.sort(arr);
    }
 
    public static void sort(long[] arr) {
        Random rgen = new Random();
        for (int i = 0; i < arr.length; i++) {
            int r = rgen.nextInt(arr.length);
            long temp = arr[i];
            arr[i] = arr[r];
            arr[r] = temp;
        }
        Arrays.sort(arr);
    }
     
    public static void sort(int[][] arr) {
        //Sort an array (immune to quicksort TLE)
        Random rgen = new Random();
        for (int i = 0; i < arr.length; i++) {
            int randomPosition = rgen.nextInt(arr.length);
            int[] temp = arr[i];
            arr[i] = arr[randomPosition];
            arr[randomPosition] = temp;
        }
        Arrays.sort(arr, new Comparator<int[]>() {
            @Override
            public int compare(int[] a, int[] b) {
                if (a[1] > b[1])
                    return 1;
                else if (a[1] < b[1])
                    return -1;
                else
                    return 0;
            }
        });
    }
}

class FastScanner {
    BufferedReader br;
    StringTokenizer st;

    public FastScanner() {
        br = new BufferedReader(new InputStreamReader(System.in), 32768);
        st = null;
    }

    String next() {
        while (st == null || !st.hasMoreElements()) {
            try {
                st = new StringTokenizer(br.readLine());
            } catch (IOException e) {
                e.printStackTrace();
            }
        }
        return st.nextToken();
    }

    int ni() {
        return Integer.parseInt(next());
    }

    int[] intArray(int N) {
        int[] ret = new int[N];
        for (int i = 0; i < N; i++)
            ret[i] = ni();
        return ret;
    }

    long nl() {
        return Long.parseLong(next());
    }

    long[] longArray(int N) {
        long[] ret = new long[N];
        for (int i = 0; i < N; i++)
            ret[i] = nl();
        return ret;
    }

    double nd() {
        return Double.parseDouble(next());
    }

    String nextLine() {
        String str = "";
        try {
            str = br.readLine();
        } catch (IOException e) {
            e.printStackTrace();
        }
        return str;
    }
}

class MultiSet {
    TreeMap<Integer, Integer> map = new TreeMap<>();
    private int size = 0;
    public MultiSet() {
    }
    public void add(int val) {
        map.put(val, map.getOrDefault(val, 0) + 1);
        size++;
    }
    public void remove(int val) {
        map.put(val, map.get(val) - 1);
        if (map.get(val) == 0) {
            map.remove(val);
        }
        size--;
    }
    public int size() {
        return size;
    }
    public Integer higher(int val) {
        return map.higherKey(val);
    }
    public Integer lower(int val) {
        return map.lowerKey(val);
    }
    public Integer ceiling(int val) {
        return map.ceilingKey(val);
    }
    public Integer floor(int val) {
        return map.floorKey(val);
    }
    public Integer first() {
        return map.firstKey();
    }
    public int last() {
        return map.lastKey();
    }
    public boolean isEmpty() {
        return map.isEmpty();
    }
}
