You are given $$$n$$$ non-negative integers $$$a_1,a_2,\ldots,a_n$$$ arranged on a ring. For each $$$1\le i \lt n$$$, $$$a_i$$$ and $$$a_{i+1}$$$ are adjacent; $$$a_1$$$ and $$$a_n$$$ are adjacent.

You need to perform the following operation exactly $$$n-1$$$ times:

Choose any pair of adjacent elements on the ring, let their values be $$$x$$$ and $$$y$$$, and merge them into a single element of value $$$\max(x,y)$$$ with cost $$$\max(x,y)$$$.

Note that this operation will decrease the size of the ring by $$$1$$$ and update the adjacent relationships accordingly.

Please calculate the minimum total cost to merge the ring into one element.

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^4$$$). The description of the test cases follows.

The first line of each test case contains an integer $$$n$$$ ($$$2\le n\le 2\cdot 10^5$$$).

The following line contains $$$n$$$ integers $$$a_1,a_2,\ldots,a_n$$$ ($$$0\le a_i \le 10^9$$$).

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2\cdot 10^5$$$.

Output

For each test case, please print a single integer — the minimum total cost.

Note

In the first test case, we can achieve a cost of $$$6$$$ on $$$[1,1,3,2]$$$ as follows:

Merge indexes $$$1$$$ and $$$2$$$ with a cost of $$$1$$$, the ring becomes $$$[1,3,2]$$$.
Merge indexes $$$1$$$ and $$$3$$$ with a cost of $$$2$$$, the ring becomes $$$[3,2]$$$.
Merge indexes $$$1$$$ and $$$2$$$ with a cost of $$$3$$$, the ring becomes $$$[3]$$$.

The total cost is $$$1+2+3=6$$$. It can be proven that it is impossible to achieve a lower cost; thus, the answer is indeed $$$6$$$.

In the second test case, the only option is to merge the two elements, with a cost of $$$2$$$.

Cyclic Merging

Examples