Migrated from Lutece 245 Matrix Multiplication

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

When calculating $A(r \times s) \times B(s \times t)$ ($A$ and $B$ are matrix),we do $r \times s \times t$ times of standard multiplication.

When calculating $A_1 \times A_2 \times \cdots \times A_N( A_i(1 \leq i \leq N)$ is matrix with size $a_i \times a_{i+1} )$,if we calculate it from left to right we will have to do $a1\cdot a2\cdot a3+a1\cdot a3\cdot a4+...+a1\cdot a_N\cdot a_{N+1}$ times of multiplications.But as is known ,matrix multiplication is associative$( (A \times B) \times C=A \times (B \times C) )$. So we can do less multiplications if we select a proper order to calculate it.

What bothers us is the minimum times of multiplications necessary to calculate $A_1 \times A_2 \times \cdots \times A_N$

Input

In the first line is an integer $T(T \leq 10)$

Followed by $T$ cases. In each case there're $2$ lines:

An integer $N(2 \leq N \leq 100)$ is given in the first line

The next line contains $N+1$ integers $a_i(1\leq a_i \leq 100)$ which define the size of matrices as described above.

Output

For each case output one integer on a single line standing for the minimum times of multiplicaions needed.

Samples

1
3
2 3 4 1

18

Note

In the Sample Input there're $3$ matrices $A_1$ $A_2$ $A_3$ with size $2 \times 3 , 3 \times 4$ and $4 \times 1$.

if we calculate $A_1 \times A_2 \times A_3$from left to right as $(A_1 \times A_2) \times A_3 , 2 \times 3 \times 4+2 \times 4 \times 1=32$ times of multiplication is needed.

if we calculate it in following way: $A_1 \times (A_2 \times A_3)$, only $3 \times 4 \times 1+2 \times 3 \times 1=18$ times of multiplications are needed ,and this is the optimal choice.

Resources

StephYDX