You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in python3.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```python
<your code here>
```

Execution time limit: 2.0 seconds
Memory limit: 256.0 MB

# Problem
You are given a string $$$s$$$ of length $$$n > 1$$$, consisting of digits from $$$0$$$ to $$$9$$$. You must insert exactly $$$n - 2$$$ symbols $$$+$$$ (addition) or $$$\times$$$ (multiplication) into this string to form a valid arithmetic expression.

In this problem, the symbols cannot be placed before the first or after the last character of the string $$$s$$$, and two symbols cannot be written consecutively. Also, note that the order of the digits in the string cannot be changed. Let's consider $$$s = 987009$$$:

- From this string, the following arithmetic expressions can be obtained: $$$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$$$. Note that the number $$$09$$$ is considered valid and is simply transformed into $$$9$$$.
- From this string, the following arithmetic expressions cannot be obtained: $$$+9 \times 8 \times 70 + 09$$$ (symbols should only be placed between digits), $$$98 \times 70 + 0 + 9$$$ (since there are $$$6$$$ digits, there must be exactly $$$4$$$ symbols).

The result of the arithmetic expression is calculated according to the rules of mathematics — first all multiplication operations are performed, then addition. You need to find the minimum result that can be obtained by inserting exactly $$$n - 2$$$ addition or multiplication symbols into the given string $$$s$$$.

## Input Format
Each test consists of multiple test cases. The first line contains a single integer $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — the number of test cases. Then follows their description.

The first line of each test case contains a single integer $$$n$$$ ($$$2 \leq n \leq 20$$$) — the length of the string $$$s$$$.

The second line of each test case contains a string $$$s$$$ of length $$$n$$$, consisting of digits from $$$0$$$ to $$$9$$$.

## Output Format
For each test case, output the minimum result of the arithmetic expression that can be obtained by inserting exactly $$$n - 2$$$ addition or multiplication symbols into the given string.

## Examples
```input
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
```
```output
10
74
0
1
9
1
19
0
11
261
0
0
0
12
93
12
24
0
```

## Note
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$$$.

Now solve the problem and return the code.