Given $n$ non-negative integers $x_1, x_2, \dots, x_n$.

For any undirected connected graph $G$ with $n$ nodes labeled from $1$ to $n$, its score is defined as: $$\text{score}(G) = \sum_{i=1}^{n} \sum_{j=i+1}^{n} \text{dist}_G(i, j)x_ix_j$$ where $\text{dist}_G(i, j)$ denotes the shortest path distance between $i$ and $j$ in graph $G$.

Your task is to output the maximum score among all undirected connected graphs with $n$ nodes.

Input

The input is read from standard input.

There are multiple test cases. The first line contains an integer $t$ ($1 \le t \le 300$), representing the number of test cases.

Each test case is described as follows: The first line contains an integer $n$ ($1 \le n \le 300$). The second line contains $n$ integers $x_1, x_2, \dots, x_n$ ($0 \le x_i \le 2,000$) describing the sequence $x$.

It is guaranteed that the sum of $n$ over all test cases does not exceed $300$.

Output

Output to standard output.

For each test case, output a single integer on a new line, representing the maximum score among all undirected connected graphs.

Examples

Input 1

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

Output 1

2
6
1044

Note 1

For the first test case, there is only one valid configuration $G = \{(1, 2)\}$. For the second test case, one optimal configuration is $G = \{(1, 2), (2, 3), (2, 4)\}$.