Time Limit: 1000 mSec Memory Limit : 32768 KB

A group of N travelers has approached an old and shabby bridge and wishes to cross the river as soon as possible. However, there can be no more than two persons on the bridge at a time. Besides it's necessary to light the way with a torch for safe crossing but the group has only one torch.

Each traveler needs t_{i} seconds to cross the river on the bridge; i=1, ... , N (t_{i} are integers from 1 to 100). If two travelers are crossing together their crossing time is the time of the slowest traveler.

The task is to determine minimal crossing time for the whole group.

The first line of the input contains a single integer T (1 <= T <= 20), the number of test cases. Then T cases follow. The first line of each case contains N, and the second line contains N integers giving the time for each traveler to cross the river. Each case is preceded by a blank line. There won't be more than 1000 people and nobody takes more than 100 seconds to cross.

For each test case, print a line containing the total number of seconds required for all the N people to cross the river.

1
4
6 7 6 5

29