Пожалуйста, прочтите новое правило об ограничении использования AI-инструментов. ×

C. Разделите выражение
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам дана строка $$$s$$$ вида <блок цифр>+<блок цифр>+...+<блок цифр>. Каждый блок цифр состоит из не менее $$$2$$$ и не более $$$13$$$ цифр; каждая цифра от $$$1$$$ до $$$9$$$.

Вам нужно разделить эту строку на выражения в форме <целое число>+<целое число>. Каждое полученное выражение должно быть непрерывной частью исходной строки, и каждый символ исходной строки должен быть включен ровно в одно выражение. Например, если у вас есть строка 123+456+789+555, то:

  • вы можете разделить ее на 123+4, 56+7 и 89+555;
  • вы не можете разделить ее на 123+456 и +789+555, так как вторая часть начинается с знака +;
  • вы не можете разделить ее на 123+4, 56+7, 8 и 9+555, так как третья часть не содержит знака +;
  • вы не можете разделить ее на 123+456+78 и 9+555, так как первая часть содержит два знака +.

Среди всех разрешенных способов разделить строку найдите тот, который максимизирует сумму результатов всех выражений, которые вы получите, и выведите эту сумму.

Входные данные

Первая строка содержит одно целое число $$$t$$$ ($$$1 \le t \le 100$$$) — количество наборов входных данных.

Каждый набор входных данных состоит из одной строки, содержащей строку $$$s$$$ ($$$5 \le |s| \le 1000$$$) в форме <блок цифр>+<блок цифр>+...+<блок цифр>. Строка содержит как минимум один знак «+». Каждый блок цифр состоит из не менее $$$2$$$ и не более $$$13$$$ цифр; каждая цифра от $$$1$$$ до $$$9$$$.

Выходные данные

Для каждого набора входных данных выведите одно целое число — максимальную возможную сумма результатов всех выражений, которые вы получите после разделения строки.

Пример
Входные данные
3
123+456+789+555
13+37
9999999999999+1111111111111+9999999999999
Выходные данные
834
50
20111111111110
Примечание

В первом наборе входных данных примера вам следует разделить строку на выражения 123+4, 56+7 и 89+555. Сумма результатов этих выражений равна $$$834$$$.

Во втором наборе входных данных примера данная строка уже является допустимым выражением и не может быть разделена дальше.