题目描述

你有一个长度 $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$ 的数字组成。

输出格式

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

输入输出样例 #1

输入 #1

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

输出 #1

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