시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 512 MB 4 4 4 100.000%

문제

You are given n segments of lengths 1, 2, . . . , 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.

입력

The first line of input contains the number of test cases z (1 ≤ z ≤ 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 ≤ n ≤ 100 000). In the second line, there are n integers 1, 2, . . . , n (1 ≤ i ≤ 109 ) – the lengths of the segments.

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

출력

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.

예제 입력 1

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

예제 출력 1

21
0
15
0