You have fallen into a Loop trap. To escape from the Loop trap, you need to solve the following puzzle:

You are given an integer sequence $a_0,a_1,\ldots,a_{n-1}$ of length $n$.

Construct an $n\times n$ grid, with both row and column indices starting from $0$. The $0$-th column, from top to bottom, is $a_0,a_1,\ldots,a_{n-1}$. Starting from the $1$-st column, each column is obtained by cyclically shifting the previous column down by one cell.

Formally, if the number in row $i$ and column $j$ is $b_{i,j}$, then

$$ b_{i,j}= \begin{cases} a_i & j=0 \\ b_{(i+n-1)\bmod n,j-1} & j>0 \end{cases} $$

You are at the upper-left corner $(0,0)$. In each step, you may only move right or down, until you reach the lower-right corner $(n-1,n-1)$. Every grid cell visited by the path is counted, including the starting and ending cells.

Please find the minimum possible sum of the weights of the grid cells visited by the path.

Input

The first line contains one positive integer $T$ $(1\leq T\leq 10^3)$, denoting the number of test cases.

For each test case, the first line contains one integer $n$ $(1\leq n\leq 10^5)$, denoting the length of the integer sequence.

The second line contains $n$ integers $a_0,a_1,\ldots,a_{n-1}$ $(0\leq a_i\leq 10^9)$, denoting the integer sequence.

It is guaranteed that, within each test file, the sum of $n$ over all test cases does not exceed $10^5$.

Output

For each test case, output one integer in one line, denoting the minimum path weight sum.

Examples

Input 1

7
4
3 4 2 1
1
7
5
8 0 9 0 1
7
5 1 9 0 0 9 9
4
1 1000 1000 1
6
4 0 9 0 1 9
3
1000000000 1000000000 1000000000

Output 1

13
7
20
30
7
24
5000000000

Note

For the first test case, the constructed grid is as follows:

$$ \begin{array}{c|c|c|c} 3 & 1 & 2 & 4 \\ \hline 4 & 3 & 1 & 2 \\ \hline 2 & 4 & 3 & 1 \\ \hline 1 & 2 & 4 & 3 \\ \end{array} $$

A path with the minimum possible sum of visited cell weights is

$$ (0,0) \to (0,1) \to (0,2) \to (1,2) \to (1,3) \to (2,3) \to (3,3). $$

Its weight sum is $3+1+2+1+2+1+3=13$. It can be verified that no valid path has a weight sum less than $13$.