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 $$$\sum_{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.

Prefix Max

Examples