Мирские цифры обозначаются заглавными латинскими буквами от A до E. Кроме того, значение буквы A равно $$$1$$$, B равно $$$10$$$, C равно $$$100$$$, D равно $$$1000$$$, E равно $$$10000$$$.
Мирское число — это последовательность мирских цифр. Значение мирского числа вычисляется следующим образом: суммируются значения всех цифр, но некоторые цифры берутся со знаком минус; цифра берется со знаком минус, если справа от нее есть цифра со значением строго больше (не обязательно сразу после нее); в противном случае цифра берется со знаком плюс.
Например, значение мирского числа DAAABDCA равно $$$1000 - 1 - 1 - 1 - 10 + 1000 + 100 + 1 = 2088$$$.
Вам дано мирское число. Вы можете изменить не более одной цифры в нем. Вычислите максимально возможное значение полученного числа.
Первая строка содержит одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных.
Единственная строка каждого набора входных данных содержит строку $$$s$$$ ($$$1 \le |s| \le 2 \cdot 10^5$$$), состоящую из заглавных латинских букв от A до E — заданное мирское число.
Сумма длин строк по всем наборам входных данных не превышает $$$2 \cdot 10^5$$$.
Для каждого набора входных данных выведите одно целое число — максимально возможное значение числа, если вы можете изменить в нем не более одной цифры.
4DAAABDCAABABCDEEDCBADDDDAAADDABECD
11088 10010 31000 15886
В первом примере можно получить EAAABDCA со значением $$$10000-1-1-1-10+1000+100+1=11088$$$.
Во втором примере можно получить EB со значением $$$10000+10=10010$$$.
Название |
---|