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

Мирские цифры обозначаются заглавными латинскими буквами от 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$$$.

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

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

Пример
Входные данные
4
DAAABDCA
AB
ABCDEEDCBA
DDDDAAADDABECD
Выходные данные
11088
10010
31000
15886
Примечание

В первом примере можно получить EAAABDCA со значением $$$10000-1-1-1-10+1000+100+1=11088$$$.

Во втором примере можно получить EB со значением $$$10000+10=10010$$$.