矩阵乘法的运算量与矩阵乘法的顺序强相关。 例如： A是一个50×10的矩阵，B是10×20的矩阵，C是20×5的矩阵 计算A*B*C有两种顺序：((AB)C)或者(A(BC))，前者需要计算15000次乘法，后者只需要3500次。 编写程序计算不同的计算顺序需要进行的乘法次数。 数据范围：矩阵个数：，行列数：，保证给出的字符串表示的计算顺序唯一。 进阶：时间复杂度：，空间复杂度：

输入描述:

输入多行，先输入要计算乘法的矩阵个数n，每个矩阵的行数，列数，总共2n的数，最后输入要计算的法则计算的法则为一个字符串，仅由左右括号和大写字母（'A'~'Z'）组成，保证括号是匹配的且输入合法！

输出描述:

输出需要进行的乘法次数