There arenpeople who wish to cross a bridge at night. At most two people can cross the bridge at the same time. There is only one flashlight and they need the flashlight to cross the bridge. So the flashlight has to be brought over to the starting side so that more people can cross.

Each person has a different crossing speed that determines the time that person would take to cross the bridge. The speed of a group is determined by the slowest member. You will have to design and code an algorithm that will determine the shortest time to cross the bridge for thenpeople under the constraints mentioned.

Input

The input will be in a file calledbridge.txt. The input file begins with a single positive integer on a line by itself that indicates the number of cases that follow. This line is followed by a blank line, and there is a blank line between two consecutive cases.

The first line of each case containsn, the number of people that will be crossing. This is followed bynlines each giving the time taken by a person to cross the bridge. Assume thatnwill never be greater than 20 and the times will be less than 60.

Ouptut

Your output will be the minimum time for each case separated by a blank line.

Sample Input

4 1 20 2 15 9 3 38 42 24 4 25 5 15 2 

Sample Output

20 15 104