Description

There are $n$ people and one boat. Everyone needs to cross the river from the left bank to the right bank. The crossing time for the $i$-th person is $a_i$. The boat can carry at most two people, and when returning from the right bank to the left bank, there must be someone on the boat. The travel time of the boat equals the maximum crossing time of the two people on board.
What is the minimum time needed for everyone to cross the river?

Input Format

Input $t$ test cases. For each test case, the first line contains $n$, and the second line contains $n$ numbers representing the crossing time for each person.

Output Format

Output $t$ lines, each containing one number representing the minimum crossing time for each test case.

Sample

1
4
1 2 5 10

17