单点时限: 2.0 sec
内存限制: 256 MB
n 个矩阵的矩阵链 A1,A2,…,An，矩阵 Ai 的规模为 pi−1×pi(1≤i≤n)，Ai 和 Ai+1是相容可乘的，求最优的完全加括号方案，使得依此次序计算矩阵链乘积：∏i=1nAi所需要的乘法次数最少。
第一行为正整数 N, 表示有 N 组测试数据。
每组测试数据的第一行为 n，表示有 n 个矩阵，2≤n≤50;
接下去的 n 行，每行有两个整数 x 和 y，表示矩阵的规模。
对行每组数据，输出一行，每行一个整数，表示最小的乘法次数。
输出的结果在 264 范围之内。
1 4 50 10 10 40 40 30 30 5
10500
一个大小为 x×y 和 y×z 的矩阵相乘所需的乘法次数为 xyz