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.