说明

给定n个矩阵${A_1，A_2，A_3，…，A_n}$，其中，$A_i$ 和$A_{i+1}（i=1，2，…，n-1）$是可乘的。矩阵乘法如下图所示。用加括号的方法表示矩阵连乘的次序，不同的计算次序计算量（乘法次数）是不同的，找出一种加括号的方法，使得矩阵连乘的计算量最小。

例如：

$A_1$是$M_{5×10}$的矩阵；

$A_2$是$M_{10×100}$的矩阵；

$A_3$是$M_{100×2}$的矩阵。

那么有两种加括号的方法：

(1)$(A_1 A_2)A_3$

(2)$A_1(A_2 A_3)$

第1种加括号方法运算量：5×10×100+5×100×2=6000。

第2种加括号方法运算量：10×100×2+5×10×2=2100。

不同的加括号办法，矩阵乘法的运算次数可能有巨大的差别！

输入格式

第一行是一个整型数m(m<100)表示共有m组测试数据。

每组测试数据的第一行是一个整数n(0<n<100)表示矩阵的个数。

第2行共n+1个整数$p_i(0<p_i<100)$，是每个矩阵的行数和最后一个矩阵的列数。

输出格式

对于每一组输入，输出矩阵连乘的最少乘法次数。

每组的输出占一行。

样例

2
5
3 5 10 8 2 4
8
4 8 12 7 9 30 4 65 52

314
16516

来源

《趣学算法》4.6节