CF1986D Mathematical Problem

你有一个长度 $n > 1$ 的字符串 $s$，由数字 $0$ 到 $9$ 组成，你要将 $n - 2$ 个运算符（$+$ 或 $\times$）插入至 $s$ 中，形成一个合法的表达式。 很明显，任何一个运算符都不应插入在 $s_0$ 前或 $s_{n - 1}$ 后，因为这样构不成一个合法的表达式。还有一点：字符串中数字的位置不能变。 假设 $s = \tt 987009$，可以获得以下几种表达式： - $ 9 \times 8 + 70 \times 0 + 9 = 81 $ - $ 98 \times 7 \times 0 + 0 \times 9 = 0 $ - $ 9 + 8 + 7 + 0 + 09 = 33 $ 表达式里的数被允许含有前导零，例子中的 $09$ 可以被转换为 $9$。 从该字符串中，无法获得以下几种表达式： - $+ 9 \times 8 \times 70 + 09$（符号只能放在数字之间） - $98 \times 70 + 0 + 9$（因为有 $6$ 个数字，所以必须正好有 $4$ 个符号）

每个测试由多个测试数据组成。第一行包含一个整数 $t$（$1 \leq t \leq 10^4$），表示测试数据的数量。 每个测试用例的第一行包含一个整数 $n(2 \leq n \leq 20)$，表示字符串 $s$ 的长度。 每个测试用例的第二行包含一个字符串 $s$，长度为 $n$，由 $0$ 到 $9$ 的数字组成。

对于每个测试数据，输出每个合法表达式的最小结果。

In the first four test cases, we cannot add symbols, so the answer will be the original number. In the fifth test case, the optimal answer looks as follows: $ 9 \times 01 = 9 \times 1 = 9 $ . In the sixth test case, the optimal answer looks as follows: $ 1 \times 01 = 1 \times 1 = 1 $ . In the seventh test case, the optimal answer looks as follows: $ 2 + 3 + 3 + 11 = 19 $ . In the eighth test case, one of the optimal answers looks as follows: $ 98 \times 7 \times 0 + 0 \times 9 = 0 $ .