Naveej is from a tribe that speaks some weird language - their alphabet consists of N distinct characters. He has associate array A=[A1,A2,…,AN], wherever Ai denotes the quantity of occurrences of the i-th character with him.
He needs to create a palindromic string exploitation all the characters he has (every character he has should be utilized in this string).
In order to create this doable, he will perform the subsequent operation:
Select associate i (1≤i≤N) and convert all occurrences of i-th alphabet to the other alphabet of his alternative.
Note that Naveej simply needs to be able to build any word, as long as each character is employed. as an example, if N=2 and A=[2,2] and that we contemplate the characters to be a and b, he will build each abba and baab, however aba isn't allowed as a result of it uses solely three characters.
Find the minimum range of operations needed specified Naveej will build a palindromic string exploitation all the characters he has. It may be verified that there continuously exists a minimum of one sequence of operations leaving the formation of a word.
Input Format
The first line of input contains one number T denoting the quantity of check cases. the outline of T check cases follows.
The first line of every test suit contains one number N - the dimensions of the alphabet.
The second line contains N space-separated integers: A1,A2,...,AN, wherever Ai is that the range of occurrences of the i-th character with Naveej.
Output Format
For each test suit, output one line containing one {integer|whole range|number} - the minimum number of operations needed so Naveej will build a palindromic string exploitation all the characters he has.
Constraints
1≤T≤1000
1≤N≤2⋅105
1≤Ai≤109
It is secured that the add of N over all check cases doesn't doesn't
Subtasks
Subtask one (100 points): Original constraints
Sample Input one
2
1
4
3
4 3 1
Sample Output one
0
1
Explanation
In the 1st test suit, N=1. Let the character be a. we will build the subsequent palindromic string: aaaa.
In the second test suit, N=3. Let the characters be a, b, c. it's at the start unattainable to create a word with the given occurrences of the characters. we tend to perform one operation: Convert all the occurrences of b to c. Then, we will build the subsequent palindromic string: acaccaca.
Code:
#include <bits/stdc++.h>
using namespace std;
#define int long long int
signed main() {
// your code goes here
int t;
cin>>t;
while(t--)
{
int n,count=0;
cin>>n;
int a[n];
for(int i=0;i<n;i++)
{
cin>>a[i];
if(a[i]%2==1)
count++;
}
cout<<count/2<<'\n';
}
return 0;
}
ConversionConversion EmoticonEmoticon