For example, there are 4 kinds of characters denoted as 'a', 'b', 'c', 'd' and the quantity of each character is {2,3,2,2} . Professor Zhang can build {"acdbbbdca"}, {"abbba", "cddc"}, {"aca", "bbb", "dcd"}, or {"acdbdca", "bb"}. The first is the optimal solution where the length of the shortest palindromic string is 9.

Note that a string is called palindromic if it can be read the same way in either direction.

The first line contains an integer n (1≤n≤105) -- the number of kinds of characters. The second line contains n integers a1,a2,...,an (0≤ai≤104).

Sample Input

Sample Output

题意：

　　开始输入T，有T组测试样例，每组测试样例给定n个数，代表n个字符的个数，每个数代表的字符是唯一确定的，将这些字符组成若干个回文串（可以一个，也可以多个），找出所有组合方式中最短 回文串 的最长长度。

　　比如第一组样例 一共有4个字符，假定为ABCD，其中A有1个，B有1个，C有2个，D有4个。组成的回文有{（CAC）（DDBDD）}或者{（A）（B）（CC）（DDDD）}等多种方式，其中第一种情况中，最短的长度为3，所以答案为3。再看题意中给出的样例，一共有4个字符，假定为ABCD，其中A有2个，B有3个，C有2个，D有2个。组成的回文有{"acdbbbdca"}, {"abbba", "cddc"}, {"aca", "bbb", "dcd"}, {"acdbdca", "bb"}。在第一种情况中，最短的长度为9，所以输出为9。

思路：

　　如果是单个的，想构成较长的回文，至少有一对字符来和他组成，组成为ABA。

　　所以，统计所有的字符中奇数的1的个数和偶数2的对数，比如一个字符有5个，则表示为2对偶数，1个奇数。

　　最后判断奇数和偶数的数量关系，如果奇数为0，偶数不为0，输出偶数*2（因为偶数是对数，不是个数），如果奇数偶数都不为0，将偶数平均分配到奇数中，表示一个奇数对应这n对偶数，输出（偶数对数/奇数个数）*2+1。

代码：

#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

#include<queue>

using namespace std;

int a[];

int main()

{

    int n;

    int m;

    cin>>m;

    for(int j=; j<m; j++)

    {

        cin>>n;

        for(int i=; i<n; i++)

            cin>>a[i];

        int ou=,ji=;

        for(int i=; i<n; i++)

        {

            if(a[i]%==)

                ji++;

            ou+=a[i]/;

        }

        if(ji==&&ou!=)

            cout<<ou*<<endl;

        else if(ji==&&ou==)

            cout<<<<endl;

        else

        {

            int ans=ou/ji;

            cout<<ans*+<<endl;

        }

    }

    return ;

}