F. Фильтр для сообщений
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
1024 мегабайта
ввод
стандартный ввод
вывод
стандартный вывод

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

Смех — это непустая строка нечётной длины, в которой чередуются одна фиксированная гласная буква и одна фиксированная согласная буква. Иначе говоря, смех имеет один из двух видов:

  • $$$vcvc\ldots v$$$ — начинается и заканчивается гласной (как ahaha);
  • $$$cvcv\ldots c$$$ — начинается и заканчивается согласной (как hahah).

Здесь $$$v$$$ — некоторая гласная буква, $$$c$$$ — некоторая согласная буква; обе буквы одни и те же на весь смех. В частности, любая одна буква является смехом. Гласными считаются буквы 'a', 'e', 'i', 'o', 'u'. Все остальные строчные латинские буквы считаются согласными (в том числе буква 'y').

Помогите Светозару с реализацией: для заданной строки $$$s$$$ из строчных латинских букв найдите самую длинную её подпоследовательность, являющуюся смехом. Если таких подпоследовательностей несколько, выведите лексикографически наименьшую.

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

Первая строка содержит целое число $$$t$$$ ($$$1 \leqslant t \leqslant 2 \cdot 10^5$$$) — количество тестовых случаев. Далее следуют $$$t$$$ описаний тестовых случаев.

Единственная строка описания содержит строку $$$s$$$ ($$$1 \leqslant |s| \leqslant 2 \cdot 10^5$$$) из строчных латинских букв.

Гарантируется, что сумма длин строк $$$s$$$ в одном входном файле не превосходит $$$2 \cdot 10^5$$$.

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

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

Пример
Входные данные
7
ahahahhahhaajajhaz
a
ab
aba
yay
ok
lolkek
Выходные данные
ahahahahaha
a
a
aba
yay
k
kek
Примечание

В примере в первом тестовом случае подходит подпоследовательность ahahahahaha. В третьем тестовом случае строка ab имеет чётную длину и не является смехом, поэтому ответ — буква 'a'. В пятом тестовом случае буква 'y' согласная, и вся строка yay является смехом.

Напомним, что подпоследовательность получается из строки удалением нуля или более символов без изменения порядка оставшихся. Последовательность $$$x$$$ лексикографически меньше последовательности $$$y$$$, если выполняется одно из двух условий:

  • для некоторого $$$i \geqslant 1$$$ верно, что $$$i$$$-й символ $$$x$$$ идёт раньше $$$i$$$-го символа $$$y$$$ по алфавиту, а все символы до $$$i$$$-го у последовательностей совпадают;
  • $$$x$$$ является префиксом $$$y$$$ и не совпадает с $$$y$$$.