CF1841C.Ranom Numbers

No, not "random" numbers.

Ranom digits are denoted by uppercase Latin letters from A to E. Moreover, the value of the letter A is $1$, B is $10$, C is $100$, D is $1000$, E is $10000$.

A Ranom number is a sequence of Ranom digits. The value of the Ranom number is calculated as follows: the values of all digits are summed up, but some digits are taken with negative signs: a digit is taken with negative sign if there is a digit with a strictly greater value to the right of it (not necessarily immediately after it); otherwise, that digit is taken with a positive sign.

For example, the value of the Ranom number DAAABDCA is $1000 - 1 - 1 - 1 - 10 + 1000 + 100 + 1 = 2088$.

You are given a Ranom number. You can change no more than one digit in it. Calculate the maximum possible value of the resulting number.

不，不是“随机”（random）数字。

“Ranom”数字由大写拉丁字母 A 到 E 表示。此外，字母 A 的值为 $1$，B 的值为 $10$，C 的值为 $100$，D 的值为 $1000$，E 的值为 $10000$。

一个 Ranom 数是一个 Ranom 数字组成的序列。Ranom 数的值按如下方式计算：将所有数字的值相加，但其中某些数字取负号：若某个数字右侧（不必紧邻）存在一个严格大于它的数字，则该数字取负号；否则取正号。

例如，Ranom 数 DAAABDCA 的值为 $1000 - 1 - 1 - 1 - 10 + 1000 + 100 + 1 = 2088$。

给你一个 Ranom 数。你最多可以修改其中的一个数字。请计算修改后所能得到的最大可能值。

The first line contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases.

The only line of each test case contains a string $s$ ($1 \le |s| \le 2 \cdot 10^5$) consisting of uppercase Latin letters from A to E — the Ranom number you are given.

The sum of the string lengths over all test cases does not exceed $2 \cdot 10^5$.

第一行包含一个整数 $t$（$1 \le t \le 10^4$）—— 测试用例的数量。

每个测试用例仅有一行，包含一个字符串 $s$（$1 \le |s| \le 2 \cdot 10^5$），该字符串由大写拉丁字母 A 到 E 组成——即你所给定的 Ranom 数。

所有测试用例中字符串长度的总和不超过 $2 \cdot 10^5$。

For each test case, print a single integer — the maximum possible value of the number, if you can change no more than one digit in it.

对于每个测试用例，输出一个整数——即在最多更改一位数字的前提下，该数字可能达到的最大值。

In the first example, you can get EAAABDCA with the value $10000-1-1-1-10+1000+100+1=11088$.

In the second example, you can get EB with the value $10000+10=10010$.

在第一个例子中，你可以得到字符串 EAAABDCA，其值为 $10000-1-1-1-10+1000+100+1=11088$。

在第二个例子中，你可以得到字符串 EB，其值为 $10000+10=10010$。