D. Математическая проблема
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам дана строка $$$s$$$ длины $$$n > 1$$$, состоящая из цифр от $$$0$$$ до $$$9$$$. Вы должны вставить в эту строку ровно $$$n - 2$$$ знака $$$+$$$ (сложение) или $$$\times$$$ (умножение), чтобы получилось корректное арифметическое выражение.

В этой задаче нельзя, чтобы знаки были перед первым или после последнего символа строки $$$s$$$, а также не может быть записано два каких-либо знака подряд. Также обращаем ваше внимание на то, что вы не меняете порядок цифр в строке. Рассмотрим $$$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 \leq t \leq 10^4$$$) — количество наборов входных данных. Далее следует их описание.

Первая строка каждого набора входных данных содержит одно целое число $$$n$$$ ($$$2 \leq n \leq 20$$$) — длина строки $$$s$$$.

Вторая строка каждого набора входных данных содержит строку $$$s$$$ длины $$$n$$$, состоящую из цифр от $$$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$$$.