Contents

• For Solution

Naveej is from a tribe that speaks some weird language – their alphabet consists of NN distinct characters. He has an array A=[A1,A2,,AN]A=[A1,A2,…,AN], where AiAi denotes the number of occurrences of the ii-th character with him.

He wants to make a palindromic string using all the characters he has (every character he has must be used in this string).

In order to make this possible, he can perform the following operation:

• Select an ii (1iN)(1≤i≤N) and convert all occurrences of ii-th alphabet to any other alphabet of his choice.

Note that Naveej just wants to be able to make any palindrome, as long as every character is used. For example, if N=2N=2 and A=[2,2]A=[2,2] and we consider the characters to be aa and bb, he can make both abbaabba and baabbaab, but abaaba is not allowed because it uses only 33 characters.

Weird Palindrome Making solution codechef

Find the minimum number of operations required such that Naveej can make a palindromic string using all the characters he has. It can be proven that there always exists at least one sequence of operations allowing for the formation of a palindrome.

Input Format

• The first line of input contains a single integer TT denoting the number of test cases. The description of TT test cases follows.
• The first line of each test case contains a single integer NN – the size of the alphabet.
• The second line contains NN space-separated integers: A1,A2,...,ANA1,A2,…,AN, where AiAi is the number of occurrences of the ii-th character with Naveej.

Weird Palindrome Making solution codechef

For each test case, output a single line containing one integer – the minimum number of operations required so that Naveej can make a palindromic string using all the characters he has.

Weird Palindrome Making solution codechef

• 1T10001≤T≤1000
• 1N21051≤N≤2⋅105
• 1Ai1091≤Ai≤109
• It is guaranteed that the sum of NN over all test cases does not exceed 21052⋅105

• Subtask 1 (100 points): Original constraints

Weird Palindrome Making solution codechef

2
1
4
3
4 3 1


Weird Palindrome Making solution codechef

0
1


Explanation

• In the first test case, N=1N=1. Let the character be aa. We can make the following palindromic string: aaaaaaaa.

• In the second test case, N=3N=3. Let the characters be aabbcc. It is initially not possible to make a palindrome with the given occurrences of the characters. We perform 1 operation: Convert all the occurrences of bb to cc. Then, we can make the following palindromic string: acaccacaacaccaca.