1135. 矩阵连乘

【问题描述】

由于矩阵乘法满足结合律，故其连乘积的计算可以有许多不同的计算次序。计算次序可以通过加括号的方式来确定。例如 $A_1A_2A_3$ 的连乘积可以有两种加括号的方式：$((A_1A_2)A_3)$和$(A_1(A_2A_3))$。

矩阵连乘积的计算次序与连乘积的计算量有关。已知两个矩阵 $A_{p\times q}$ 和 $A_{q\times r}$ 相乘的计算量为 $p\times q \times r$，请确定矩阵连乘积 $A_1 A_2\cdots A_n$ 的最小计算量的计算次序。

【输入格式】

输入的第一行为数据组数 $m(1\leq m\leq 6)$。

接下来有 $m$ 组数据，每组数据包含两行。

第一行为矩阵的个正整数 $n(1\leq n\leq 10)$。

接下来有 $n+1$ 个正整数 $P_0,P_1,P_2,\cdots,P_n$，表示矩阵的维数，其中第 $i$ 个矩阵的维数为 $P_{i-1}\times P_i$。

【输出格式】

共有 $m$ 组，每组包含两行。

第一行为矩阵连乘积的最小计算量，保证计算量不超过 $10^6$。

第二行为矩阵连乘积的计算顺序。

【输入样例】

2
2
2 3 5
3
2 5 100 2

【输出样例】

30
(A1A2)
1020
(A1(A2A3))