1135. 矩阵连乘

【问题描述】

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

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

【输入格式】

输入的第一行为数据组数$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))