Crossing the Bridge

Problem Background

Special for beginners, ^_^

Problem Description

On a dark and windy night, $n\ (n\le 1000)$ children are on one side of a bridge and need to cross it. The bridge is narrow and at most two people may cross at a time. They have only one flashlight, so after every two people cross, one must bring the flashlight back. What is the minimum total time needed for everyone to cross?

Input Format

There are $t$ test cases. For each case, the first line contains $n\ (n<1000)$, and the second line contains $n$ integers — the crossing time of each person.

Output Format

Output $t$ lines, each with one integer — the minimum crossing time for that case.

Sample Input

1
4
1 2 5 10

Sample Output

17

Constraints

$n<1000$.

Time limit 1s, memory limit 1024KiB for each test case.