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.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.math.BigInteger;
import java.util.*;
public class Cp {
	public static int primeFactors(int number) {
		  int n = number;
		  int count = 0;
		  for (int i = 2; i <= n; i++) {
		   while (n % i == 0) {
			   count++;
			   n /= i;
		   }
		  }
		  return count;
		 }
	
	public static void main(String[] args) {
		 
		
		int t = sc.nextInt();
		while(t-->0) {
			
			int n = sc.nextInt();
			int a[] = new int[n];
			Map<Integer,Integer> map = new HashMap<>();
			for(int i = 0;i<n;i++) {
				int k = sc.nextInt();
				a[i] = k;
				if(map.containsKey(k)) {
					map.put(k, map.get(k)+1);
				}else {
					map.put(k, 1);
				}
			}
			int max = 0;
			for(Map.Entry<Integer, Integer> m  : map.entrySet()) {
				if(m.getValue()>max) {
					max = m.getValue();
				}
			}
			if(2*max>n) {
				System.out.println(2*max-n);
			}else {
				if(n%2==0) {
					System.out.println(0);
				}else {
					System.out.println(1);
				}
			}
			}
	}

static FastReader sc=new FastReader(); 
static int dp[][];
static int mod=1000000007;

public static long Pow(long base, long exp) {

	 if (exp == 0)
	 return 1;

	 else if (exp == 1)
	 return base;

	 else if (exp%2 == 0)
	 return Pow(base*base, exp/2);

	 else
	 return base*Pow(base, exp-1);
	}
public static long modPow(long base, long exp, long n) {

	 base = base%n;

	 if (exp == 0)
	 return 1;

	 else if (exp == 1)
	 return base;

	 else if (exp%2 == 0)
	 return modPow(base*base%n, exp/2, n);

	 else
	 return base*modPow(base, exp-1, n)%n;
	}

static int go(int A[],int B[],int gcd,int i) {
	if(i==A.length) {
		for(int j=2;j*j<=gcd;j++) {
			if(gcd%j==0) {
				return j;
			}
		}
		return -1;
	}
	
	int g=gcd(A[i],gcd);
	int h=gcd(B[i],gcd);
	int op1=go(A, B, g, i+1);
	if(op1==-1) {
		op1=go(A, B, h, i+1);
		return op1;
	}
	else
		return op1;
}
static int[] input(int n) {
	int A[]=new int[n];
	for(int i=0;i<n;i++) {
		A[i]=sc.nextInt();
	}
	return A;
}
static long[] inputL(int n) {
	long A[]=new long[n];
	for(int i=0;i<n;i++) {
		A[i]=sc.nextLong();
	}
	return A;
}
static String[] inputS(int n) {
	String A[]=new String[n];
	for(int i=0;i<n;i++) {
		A[i]=sc.next();
	}
	return A;
}
static long sum(int A[]) {
	long sum=0;
	for(int i : A) {
		sum+=i;
	}
	return sum;
}
static long sum(long A[]) {
	long sum=0;
	for(long i : A) {
		sum+=i;
	}
	return sum;
}
static void input(int A[],int B[]) {
	for(int i=0;i<A.length;i++) {
		A[i]=sc.nextInt();
		B[i]=sc.nextInt();
	}
}
static int[][] input(int n,int m){
	int A[][]=new int[n][m];
	for(int i=0;i<n;i++) {
		for(int j=0;j<m;j++) {
			A[i][j]=i();
		}
	}
	return A;
}
static char[][] charinput(int n,int m){
	char A[][]=new char[n][m];
	for(int i=0;i<n;i++) {
		String s=s();
		for(int j=0;j<m;j++) {
			A[i][j]=s.charAt(j);
		}
	}
	return A;
}
static int max(int A[]) {
	int max=Integer.MIN_VALUE;
	for(int i=0;i<A.length;i++) {
		max=Math.max(max, A[i]);
	}
	return max;
}
static int min(int A[]) {
	int min=Integer.MAX_VALUE;
	for(int i=0;i<A.length;i++) {
		min=Math.min(min, A[i]);
	}
	return min;
}
static long max(long A[]) {
	long max=Long.MIN_VALUE;
	for(int i=0;i<A.length;i++) {
		max=Math.max(max, A[i]);
	}
	return max;
}
static long min(long A[]) {
	long min=Long.MAX_VALUE;
	for(int i=0;i<A.length;i++) {
		min=Math.min(min, A[i]);
	}
	return min;
}
static long [] prefix(long A[]) {
	long p[]=new long[A.length];
	p[0]=A[0];
	for(int i=1;i<A.length;i++)
		p[i]=p[i-1]+A[i];
	return p;
}
static long [] prefix(int A[]) {
	long p[]=new long[A.length];
	p[0]=A[0];
	for(int i=1;i<A.length;i++)
		p[i]=p[i-1]+A[i];
	return p;
}
static long [] suffix(long A[]) {
	long p[]=new long[A.length];
	p[A.length-1]=A[A.length-1];
	for(int i=A.length-2;i>=0;i--)
		p[i]=p[i+1]+A[i];
	return p;
}
static long [] suffix(int A[]) {
	long p[]=new long[A.length];
	p[A.length-1]=A[A.length-1];
	for(int i=A.length-2;i>=0;i--)
		p[i]=p[i+1]+A[i];
	return p;
}
static long mod(long x) {
	int mod=1000000007;
	return ((x%mod + mod)%mod);
}
static String reverse(String s) {
	StringBuffer p=new StringBuffer(s);
	p.reverse();
	return p.toString();
}

static int i() {
	return sc.nextInt();
}
static String s() {
	return sc.next();
}
static long l() {
	return sc.nextLong();
}  
static void sort(int[] A){
	int n = A.length;
	Random rnd = new Random();
	for(int i=0; i<n; ++i){
		int tmp = A[i];
		int randomPos = i + rnd.nextInt(n-i);
		A[i] = A[randomPos];
		A[randomPos] = tmp;
	}
	Arrays.sort(A);
}
static void sort(long[] A){
	int n = A.length;
	Random rnd = new Random();
	for(int i=0; i<n; ++i){
		long tmp = A[i];
		int randomPos = i + rnd.nextInt(n-i);
		A[i] = A[randomPos];
		A[randomPos] = tmp;
	}
	Arrays.sort(A);
}
static String sort(String s) {
	Character ch[]=new Character[s.length()];
	for(int i=0;i<s.length();i++) {
		ch[i]=s.charAt(i);
	}
	Arrays.sort(ch);
	StringBuffer st=new StringBuffer("");
	for(int i=0;i<s.length();i++) {
		st.append(ch[i]);
	}
	return st.toString();
}
static HashMap<Integer,Integer> hash(int A[]){
	HashMap<Integer,Integer> map=new HashMap<Integer, Integer>();
	for(int i : A) {
		if(map.containsKey(i)) {
			map.put(i, map.get(i)+1);
		}
		else {
			map.put(i, 1);
		}
	}
	return map;
}
static TreeMap<Integer,Integer> tree(int A[]){
	TreeMap<Integer,Integer> map=new TreeMap<Integer, Integer>();
	for(int i : A) {
		if(map.containsKey(i)) {
			map.put(i, map.get(i)+1);
		}
		else {
			map.put(i, 1);
		}
	}
	return map;
}
static boolean prime(int n) 
{ 
	if (n <= 1) 
		return false; 
	if (n <= 3) 
		return true; 
	if (n % 2 == 0 || n % 3 == 0) 
		return false; 
	double sq=Math.sqrt(n);
	
	for (int i = 5; i <= sq; i = i + 6) 
		if (n % i == 0 || n % (i + 2) == 0) 
			return false; 
	return true; 
} 
static boolean prime(long n) 
{ 
	if (n <= 1) 
		return false; 
	if (n <= 3) 
		return true; 
	if (n % 2 == 0 || n % 3 == 0) 
		return false; 
	double sq=Math.sqrt(n);
	
	for (int i = 5; i <= sq; i = i + 6) 
		if (n % i == 0 || n % (i + 2) == 0) 
			return false; 
	return true; 
} 
static int gcd(int a, int b) 
{ 
	if (a == 0) 
		return b; 
	return gcd(b % a, a); 
} 
static long gcd(long a, long b) 
{ 
	if (a == 0) 
		return b; 
	return gcd(b % a, a); 
} 
static class Pair implements Comparable<Pair>
{
	int x;
	int y;
	Pair(int x,int y){
		this.x=x;
		this.y=y;
	}
	@Override
	public int compareTo(Pair o) {
		if(this.x>o.x)
			return 1;
		else if(this.x<o.x)
			return -1;
		else {
			if(this.y>o.y)
				return 1;
			else if(this.y<o.y)
				return -1;
			else
				return 0;
		}
	}
}
static class FastReader 
{ 
	BufferedReader br; 
	StringTokenizer st; 
	
	public FastReader() 
	{ 
		br = new BufferedReader(new
				InputStreamReader(System.in)); 
	} 
	
	String next() 
	{ 
		while (st == null || !st.hasMoreElements()) 
		{ 
			try
			{ 
				st = new StringTokenizer(br.readLine()); 
			} 
			catch (IOException  e) 
			{ 
				e.printStackTrace(); 
			} 
		} 
		return st.nextToken(); 
	} 
	int nextInt() 
	{ 
		return Integer.parseInt(next()); 
	} 
	
	long nextLong() 
	{ 
		return Long.parseLong(next()); 
	} 
	
	double nextDouble() 
	{ 
		return Double.parseDouble(next()); 
	} 
	
	String nextLine() 
	{ 
		String str = ""; 
		try
		{ 
			str = br.readLine(); 
		} 
		catch (IOException e) 
		{ 
			e.printStackTrace(); 
		} 
		return str; 
	} 
} 



static int multiply(int x, int res[], int res_size) {

	int carry = 0;

	
	for (int i = 0; i < res_size; i++) {
	int prod = res[i] * x + carry;

	
	res[i] = prod % 10;

	carry = prod / 10;
	}


	while (carry > 0) {
	res[res_size] = carry % 10;
	carry = carry / 10;
	res_size++;
	}
	return res_size;
}

public static void power(int x, int n) {
	
	if(n == 0 ){
	System.out.print("1");
	return;
}
	
	int MAX = 1000001;
	int res[] = new int[MAX];
	int res_size = 0;
	int temp = x;

	while (temp != 0) {
	res[res_size++] = temp % 10;
	temp = temp / 10;
	}

	
	for (int i = 2; i <= n; i++)
	res_size = multiply(x, res, res_size);

	System.out.print(x + "^" + n + " = ");
	for (int i = res_size - 1; i >= 0; i--)
	System.out.print(res[i]);
}


} 




