Ranom 数字

• 时间限制：2 秒
• 内存限制：256 MiB

题目描述

Ranom 数字由大写字母 A 到 E 组成，各字母的数值依次为 $1,10,100,1000,10000$。

一个字符串的值按如下规则计算：若某个字符右侧存在数值严格大于它的字符，则该字符贡献其数值的相反数；否则贡献其数值。字符串的值是所有字符贡献之和。

例如，DAAABDCA 的值为

你至多可以把字符串中的一个字符改成 A 到 E 中的任意字符。求修改后可能得到的最大值；也可以不修改。

输入格式

第一行一个整数 $t$，表示测试用例数。

接下来 $t$ 行，每行一个仅由 A 到 E 组成的非空字符串 $s$。

输出格式

对每个测试用例输出一行一个整数，表示至多修改一个字符后能得到的最大值。

样例输入 1

4
DAAABDCA
AB
ABCDEEDCBA
DDDDAAADDABECD

样例输出 1

11088
10010
31000
15886

数据范围

对所有数据：

• $1\le t\le10^4$；
• $1\le |s|\le2\times10^5$；
• 单个输入文件内所有字符串长度之和不超过 $2\times10^5$。

本题采用独立测试点计分，每个测试点等分；通过一个测试点中的全部测试用例才能获得该点分数。

提示

从右向左处理字符串时，一个字符贡献的正负只取决于它与右侧最大字符的大小关系。还需记录是否已经使用过修改机会。