Mabư Béo chào các bạn, các bạn đã sẵn sàng cùng Mabư Béo khám phá những điều thú vị đang chờ đón các bạn trên chuyến phiêu lưu này chưa?

Cho ~N~ que diêm. Que diêm thứ ~i~ có độ dài là ~l_i~.

Mabư Béo dùng một số que diêm để ghép thành đa giác lồi. Hỏi, đa giác lồi với chu vi lớn nhất hắn ta có thể tạo được có chu vi là bao nhiêu?

Trong trường hợp Mabư Béo không thể tạo thành một đa giác lồi nào từ các que diêm đã cho, in ra ~0~.

Input

Dòng đầu tiên chứa ~T~ (~1 \le T \le 100~) - số test trong một tệp đầu vào. Mỗi test sẽ có định dạng như sau:

• Dòng thứ nhất chứa ~N~ (~3 \le N \le 100~) - số que diêm mà Majin Buu có.

• Dòng thứ hai chứa ~N~ số: ~l_1, l_2, \ldots, l_N~ (~1 \le l_i \le 10^6~) - độ dài các que diêm.

Output

Với mỗi bộ test, nếu không thể tạo thành một đa giác lồi nào từ các que diêm đã cho, in ra ~0~. Ngược lại, in ra chu vi của đa giác lớn nhất Mabư Béo có thể tạo được.

Sample Input 1

4
6
9 3 4 5 50 6
3
1 2 4
7
13 8 5 3 2 1 1
10
1 2 4 8 16 32 64 128 256 512

Sample Output 1

27
0
33
0

Notes

Ở ví dụ đầu tiên, có thể xếp các que diêm có chỉ số lần lượt là: ~1, 2, 3, 4, 6~ thành đa giác như sau: