矩阵连乘
Time Limit: 1000 MSMemory Limit: 5000 KB

Description

两个矩阵A(r行s列)和B(s行t列)相乘, 乘法代价为r*s*t. 现给定N(N<=500)个矩阵连乘问题, 请计算最小乘法代价。

Input

第一行输入M(M<=10)表示有M组数据。每组数据第一行输入N,表示矩阵个数;接下来一行输入N个矩阵的行数和列数。

Output

输出M行正整数,第i行表示第i组数据的最小乘法代价。

Sample Input

2
3
1 2 2 3 3 4
3
4 3 3 2 2 1 

Sample Output

18
18
Submit Your Code                        Discuss



苏ICP备2022026913号-1