D. 数学问题

时间限制：2 秒
内存限制：256 兆字节

给定一个长度为 $n>1$ 的字符串 $s$，由数字 $0$ 到 $9$ 组成。你必须在这个字符串中恰好插入 $n-2$ 个符号（加法 $+$ 或乘法 $\times$），以形成一个合法的算术表达式。

在本题中，符号不能放在字符串的第一个字符之前或最后一个字符之后，且不能有两个符号连续出现。此外，字符串中数字的顺序不能改变。考虑 $s=987009$：

• 从这个字符串可以得到以下算术表达式：$9 \times 8 + 70 \times 0 + 9 = 81$，$98 \times 7 \times 0 + 0 \times 9 = 0$，$9 + 8 + 7 + 0 + 09 = 9 + 8 + 7 + 0 + 9 = 33$。注意数字 $09$ 被视为有效，并且简单地转换为 $9$。
• 从这个字符串不能得到以下算术表达式：$+9 \times 8 \times 70 + 09$（符号只能放在数字之间），$98 \times 70 + 0 + 9$（因为有 $6$ 位数字，必须恰好有 $4$ 个符号）。

算术表达式的结果按照数学规则计算——先执行所有乘法运算，然后执行加法。你需要找出通过向给定字符串 $s$ 中恰好插入 $n-2$ 个加法或乘法符号所能得到的最小结果。

输入

每个测试包含多个测试用例。第一行包含一个整数 $t$（$1 \le t \le 10^4$）——测试用例的数量。接下来是它们的描述。

每个测试用例的第一行包含一个整数 $n$（$2 \le n \le 20$）——字符串 $s$ 的长度。

第二行包含一个长度为 $n$ 的字符串 $s$，由数字 $0$ 到 $9$ 组成。

输出

对于每个测试用例，输出通过向给定字符串中恰好插入 $n-2$ 个加法或乘法符号所能得到的算术表达式的最小结果。

示例

输入

18
2
10
2
74
2
00
2
01
3
901
3
101
5
23311
6
987009
7
1111111
20
99999999999999999999
20
00000000000000000000
4
0212
18
057235283621345395
4
1112
20
19811678487321784121
4
1121
4
2221
3
011

输出

10
74
0
1
9
1
19
0
11
261
0
0
0
12
93
12
24
0

注释

在前四个测试用例中，我们无法添加符号，因此答案就是原始数字。

在第五个测试用例中，最优答案如下：$9 \times 01 = 9 \times 1 = 9$。

在第六个测试用例中，最优答案如下：$1 \times 01 = 1 \times 1 = 1$。

在第七个测试用例中，最优答案如下：$2 + 3 + 3 + 11 = 19$。

在第八个测试用例中，一个最优答案如下：$98 \times 7 \times 0 + 0 \times 9 = 0$。