E. Наибольшее красивое число
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Ага, это очередная задача с определением «красивых» чисел.

Назовем положительное целое число x красивым, если его десятичное представление без лидирующих нулей содержит четное количество цифр, и существует перестановка этого представления, которая является палиндромом. Например, число 4242 красивое, так как оно содержит 4 цифры, и существует перестановка 2442, которая является палиндромом.

Для заданного положительного целого числа s, найдите наибольшее красивое число, которое строго меньше s.

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

В первой строке записано одно целое число t (1 ≤ t ≤ 105) — количество наборов входных данных, которые вам предстоит решить.

Затем следуют t строк, каждая содержит десятичное представление очередного числа s. Гарантируется, что это — строка четной длины, не содержащая лидирующих нулей, а также существует хотя бы одно красивое число строго меньше s.

Сумма длин s по всем наборам входных данных не превосходит 2·105.

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

Для каждого набора входных данных выведите в отдельной строке наибольшее красивое число, которое строго меньше s (гарантируется, что ответ существует).

Пример
Входные данные
4
89
88
1000
28923845
Выходные данные
88
77
99
28923839