Задача I. Imictcoin ≡

Условие

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

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

Например:

• s = «abababc» — верный хэш;
• s = «aabcabab» — неверный хэш;
• s = «a» — верный хэш.

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

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

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

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

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

• -1, если верный хэш не может быть получен;
• строку, представляющую из себя верный хэш, который является перестановкой символов строки s_i.

Ограничения

1 ≤ T ≤ 10⁴.

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

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

2
aabb
aaaabb

abab
-1

1
a

a