Description

Several people need to cross a river. Each time, two people cross together and one returns. The speed is determined by the slower person. Determine the minimum total time required for everyone to cross.

Input Format

Input consists of t test cases. For each test case, the first line contains an integer n, and the second line contains n integers representing the crossing times of each person.

Output Format

Output t lines, each containing a single integer representing the minimum total crossing time for the corresponding test case.

1
4
1 2 5 10

17