Source

This problem is adapted from Long Long OJ. All rights reserved.

Problem Description

As we all know, little naive has $n$ bottles arranged in a row on a table. The color of the $i$-th bottle is $c_i$. Each bottle has a spiritual essence, and in each operation, you can choose two adjacent bottles, pay a cost equal to the product of the numerical values of their colors, and change the color of one bottle to match the color of the other.

Now, little naive wants to make all bottles have the same color (with no limit on the number of operations), but the total cost of the operations must be minimized.

Input Format

This problem contains multiple test cases.

The first line contains a positive integer $T$, representing the number of test cases.

For each test case:

• The first line contains an integer $n$, representing the number of bottles.
• The second line contains $n$ integers, where the $i$-th integer is the color $c_i$ of the $i$-th bottle.

Output Format

For each test case, output a single line with an integer representing the minimum total cost.

Samples

1
4
7 4 6 10

92

Sample Explanation

The initial state is $\{7, 4, 6, 10\}$:

• First operation: $\{7, 4, 6, 10\} \to \{4, 4, 6, 10\}$, with a cost of $7 \times 4 = 28$.
• Second operation: $\{4, 4, 6, 10\} \to \{4, 4, 4, 10\}$, with a cost of $4 \times 6 = 24$.
• Third operation: $\{4, 4, 4, 10\} \to \{4, 4, 4, 4\}$, with a cost of $4 \times 10 = 40$.

The total cost is $28 + 24 + 40 = 92$.

Data Range

$1 \le T \le 10$, $1 \le n \le 300$, $1 \le c_i \le 2 \times 10^5$.