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
//
//  main.cpp
//  D - Epic Transformation
//
//  Created by LiZnB on 2021/3/25.
//
#include <cstdio>
#include <cstring>
#include <algorithm>

#define ls tree[pos].l
#define rs tree[pos].r
using namespace std;

const int INF = 0x3f3f3f3f;
const int N = 200000 + 10;

int arr[N];

struct Node {
    int l, r;
    long long val;
    int real;
};

Node max(Node a, Node b) {
    if (a.val > b.val) return a;
    return b;
}

struct Tree {
    Node tree[N * 4];
    
    void Built(int L, int R, int pos) {
        ls = L;
        rs = R;
        if (L == R) {
            tree[pos].val = arr[L];
            tree[pos].real = L;
            return;
        }
        int m = L + (R - L) / 2;
        Built(L, m, pos << 1);
        Built(m + 1, R, pos << 1 | 1);
        if (tree[pos << 1].val > tree[pos << 1 | 1].val) {
            tree[pos].val = tree[pos << 1].val;
            tree[pos].real = tree[pos << 1].real;
        } else {
            tree[pos].val  = tree[pos << 1 | 1].val;
            tree[pos].real = tree[pos << 1 | 1].real;
        }
    }
    
    void Modify(int pos, int p, long long val) {
        if (rs == p && ls == p) {
            tree[pos].val += val;
            return;
        }
        int m = ls + (rs - ls) / 2;
        if (p <= m) Modify(pos << 1, p, val);
        if (p > m) Modify(pos << 1 | 1, p, val);
        if (tree[pos << 1].val > tree[pos << 1 | 1].val) {
            tree[pos].val = tree[pos << 1].val;
            tree[pos].real = tree[pos << 1].real;
        } else {
            tree[pos].val  = tree[pos << 1 | 1].val;
            tree[pos].real = tree[pos << 1 | 1].real;
        }

    }
    
    Node Query(int pos, int L, int R) {
        if (ls >= L && rs <= R) {
            return tree[pos];
        };
        int m = ls + (rs - ls) / 2;
        Node ans;
        ans.val = -INF;
        if (m >= L) {
            ans = max(Query(pos << 1, L, R), ans);
        }
        if (m < R) {
            ans = max(Query(pos << 1 | 1, L, R), ans);
        }
        if (tree[pos << 1].val > tree[pos << 1 | 1].val) {
            tree[pos].val = tree[pos << 1].val;
            tree[pos].real = tree[pos << 1].real;
        } else {
            tree[pos].val  = tree[pos << 1 | 1].val;
            tree[pos].real = tree[pos << 1 | 1].real;
        }

        return ans;
    }
    
} T;
int d[N];
int main() {
    int t;
    scanf("%d", &t);
    while (t--) {
        int n;
        scanf("%d", &n);
        for (int i = 1; i <= n; i++) {
            scanf("%d", &d[i]);
        }
        sort(d + 1, d + n + 1);
        int p = 1;
        arr[1] = 1;
        for (int i = 2; i <= n; i++) {
            if (d[i - 1] != d[i]) {
                p++;
                arr[p] = 1;
            }
            else {
                arr[p]++;
            }
        }
        T.Built(1, p, 1);
        int ans = n;
        for (int i = 1; i <= n; i++) {
            Node f1 = T.Query(1, 1, p);
            T.Modify(1, f1.real, -f1.val);
            Node f2 = T.Query(1, 1, p);
            T.Modify(1, f1.real, f1.val);
            
            if (f1.val == 0 || f2.val == 0) break;
            T.Modify(1, f1.real, -1);
            T.Modify(1, f2.real, -1);
            ans -= 2;
        }
        printf("%d\n", ans);
    }
    
    return 0;
}
