给您一个字符串 $$$s$$$,其形式为<数字块>+<数字块>+...+<数字块>。每个数字块至少由 $$$2$$$ 和最多 $$$13$$$ 数字组成;每个数字都是从 $$$1$$$ 到 $$$9$$$。
您必须将此字符串拆分为 <integer>+<integer> 形式的表达式。每个表达式必须是给定字符串的连续部分,并且给定字符串的每个字符必须恰好属于一个表达式。例如,如果您有字符串 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$$$。
输出
对于每个测试用例,打印一个整数 - 分割字符串后得到的所有表达式结果的最大可能总和。
示例
输入 #1
3 123+456+789+555 13+37 9999999999999+1111111111111+9999999999999
输出 #1
834 50 20111111111110
注意
在示例的第一个测试用例中,您应该将字符串拆分为表达式 123+4、56+7 和 89+555。这些表达式的结果之和为 $$$834$$$。
在示例的第二个测试用例中,给定的字符串已经是有效的表达式,无法进一步拆分。