Description

You are given $n$ segments of lengths $\ell_1, \ell_2, \ldots, \ell_n$, respectively. Determine the largest possible circumference of a convex polygon that can be constructed using these segments (in any order, and not neccessarily all of them). The polygon must be non-degenerate – in other words, its area must be positive.

Input Format

The first line of input contains the number of test cases $z$ ($1 \le z \le 100\,000$). The test cases follow, each one in the following format:

• The first line of a test case contains the number of segments $n$ ($1 \le n \le 100\,000$).
• In the second line, there are $n$ integers $\ell_1, \ldots, \ell_n$ ($1 \le \ell_i \le 10^9$) – the lengths of the segments.

The sum of $n$ values over all test cases does not exceed $1\,000\,000$.

Output Format

For each test case, output a single integer – the largest possible circumference of a convex polygon made of given segments. If no such polygon can be constructed at all, output $0$.

4
6
1 2 3 4 5 6
3
9 5 14
4
5 15 4 6
2
10 11

21
0
15
0