You are given an array of $n$ integers $a_1, a_2, \ldots, a_n$.

The value of an array is the sum of the maximums of each prefix of the array. More formally, the value of an array $a$ is $um_{i=1} ^{n} \operatorname{max}(a_1, \ldots, a_i)$. For example, the value of the array [$1, 2, 1$] is $\operatorname{max}(1) + \operatorname{max}(1, 2) + \operatorname{max}(1, 2, 1) = 1 + 2 + 2 = 5$.

You can choose two indices $i$ and $j$ and swap elements $a_i$ and $a_j$; this operation can be applied at most one time.

Find the maximum possible value of the array $a$ after at most one operation.

Input

The first line of the input contains a single integer $t$ ($1 \leq t \leq 100$) — the number of test cases.

The first line of each test case contains a single integer $n$ ($2 \le n \le 50$) — the length of the array $a$.

The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le 10^4$) — the array $a$.

Output

For each test case, output the maximum possible value of the array $a$ after the swap has been performed.

Note

For the first test case, we can swap $a_1$ with $a_4$ to get the array [$5, 1, 4, 2, 3$], which has a value of $\operatorname{max}(5) + \operatorname{max}(5, 1) + \operatorname{max}(5, 1, 4) + \operatorname{max}(5, 1, 4, 2) + \operatorname{max}(5, 1, 4, 2, 3) = 25$.

For the second test case, the current value of the array is $\operatorname{max}(5) + \operatorname{max}(5, 1) = 10$. If we were to swap $a_1$ and $a_2$, $a$ would be equal to [$1, 5$], which has a value of $\operatorname{max}(1) + \operatorname{max}(1, 5) = 6$, meaning the best option is to not perform a swap.

Samples

4
5
2 1 4 5 3
2
5 1
3
3 2 1
2
6 7

25
10
9
14