单点时限: 2.0 sec
内存限制: 256 MB
$n$ 个矩阵的矩阵链 $A_1, A_2, \dots, A_n$，矩阵 $A_i$ 的规模为 $p_{i-1} \times p_i (1\leq i\leq n)$，$A_i$ 和 $A_{i+1}$是相容可乘的，求最优的完全加括号方案，使得依此次序计算矩阵链乘积：$\prod_{ i = 1 }^n A_i$所需要的乘法次数最少。
第一行为正整数 $N$, 表示有 $N$ 组测试数据。
每组测试数据的第一行为 $n$，表示有 $n$ 个矩阵，$2\leq n\leq50$;
接下去的 $n$ 行，每行有两个整数 $x$ 和 $y$，表示矩阵的规模。
对行每组数据，输出一行，每行一个整数，表示最小的乘法次数。
输出的结果在 $2^{64}$ 范围之内。
1 4 50 10 10 40 40 30 30 5
10500
一个大小为 $x \times y$ 和 $y \times z$ 的矩阵相乘所需的乘法次数为 $xyz$