Задача I. Imictcoin

Входной файл:Стандартный вход   Ограничение времени:1 сек
Выходной файл:Стандартный выход   Ограничение памяти:512 Мб

Условие

В связи с образованием нового института в одном небезызвестном университете, его лучшие программисты решили создать свою крипто монету «Имикткоин». Но главный специалист по компьютерной безопасности Сергей придумал специальные правила по которым должен подбираться хэш для каждого следующего блока в блокчейне.

Хэш должен представлять из себя строку, состоящую из строчных букв латинского алфавита, которая должна удовлетворять одному единственному условию — ни один символ не встречается два раза подряд.

Например:

Требуется написать программу, которая преобразует входную строку в верный хэш путём перестановок символов в ней либо определит, что сделать это невозможно.

Формат входных данных

В первой строке записано одно целое число T — количество строк. Далее следуют T строк si, по одной в строке данных. Строки состоят из строчных букв латинского алфавита.

Формат выходных данных

Для каждой строки si выведите в отдельной строке:

Ограничения

1 ≤ T ≤ 104.

Длина si не превышает 5⋅ 105. Сумма длин всех строк s во всех наборах входных данных теста не превышает 5⋅ 105.

Примеры тестов

Стандартный вход Стандартный выход
1
2
aabb
aaaabb
abab
-1
2
1
a
a

0.231s 0.121s 15