Keep On Movin

Zhang 교수에게는 $n$종류의 문자가 있고, $i$번째 문자의 개수는 $a_i$이다. Zhang 교수는 모든 문자를 사용해 여러 개의 회문을 만들려고 한다. 그는 또한 가장 짧은 회문의 길이를 최대화하려고 한다.

예를 들어, 'a', 'b', 'c', 'd' 네 종류의 문자가 있고 각각의 개수가 $\{2, 3, 2, 2\}$라고 하자. Zhang 교수는 ("acdbbbdca")를 만들거나, ("abbba"와 "cddc")를 만들거나, ("aca", "bbb", "dcd")를 만들거나, ("acdbdca"와 "bb")를 만들 수 있다. 첫 번째가 가장 짧은 회문의 길이가 $9$인 최적의 방법이다.

문자열을 양방향에서 읽어도 같으면 회문이라고 한다.

여러 개의 테스트 케이스가 주어진다. 입력의 첫 줄에는 테스트 케이스의 수를 나타내는 정수 $T$가 주어진다. 각 테스트 케이스는 다음과 같다.

첫 줄에는 문자의 종류 수를 나타내는 정수 $n$ ($1 \le n \le 10^5$)이 주어진다. 둘째 줄에는 $n$개의 정수 $a_1, a_2, \ldots, a_n$ ($0 \le a_i \le 10^4$)이 주어진다.

테스트 케이스는 최대 $110$개이고, 입력의 총 크기는 최대 $6$ 메비바이트이다.

각 테스트 케이스마다 답을 나타내는 정수를 한 줄에 출력한다.