F. Message Filter
time limit per test
2 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

Svetozar often chats with his friends in messaging apps. He dislikes typos, so he decided to clean them out of messages that look like laughter.

Laughter is a non-empty string of odd length in which one fixed vowel and one fixed consonant alternate. In other words, laughter has one of two forms:

  • $$$vcvc\ldots v$$$ starts and ends with a vowel (like ahaha);
  • $$$cvcv\ldots c$$$ starts and ends with a consonant (like hahah).

Here $$$v$$$ is some vowel and $$$c$$$ is some consonant; both letters are the same throughout the laughter. In particular, any single letter is laughter. The vowels are the letters 'a', 'e', 'i', 'o', and 'u'. All other lowercase English letters are considered consonants (including the letter 'y').

Help Svetozar implement this: for a given string $$$s$$$ of lowercase English letters, find its longest subsequence that is laughter. If there are several such subsequences, print the lexicographically smallest one.

Input

The first line contains an integer $$$t$$$ ($$$1 \leq t \leq 2 \cdot 10^5$$$): the number of test cases. Then, $$$t$$$ test cases follow.

The only line of a test case contains a string $$$s$$$ ($$$1 \leq |s| \leq 2 \cdot 10^5$$$) of lowercase English letters.

It is guaranteed that the sum of the lengths of the strings $$$s$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

Output

For each test case, print the required subsequence on a separate line. If there are several suitable subsequences of maximum length, print the lexicographically smallest of them.

Example
Input
7
ahahahhahhaajajhaz
a
ab
aba
yay
ok
lolkek
Output
ahahahahaha
a
a
aba
yay
k
kek
Note

In the first test case of the sample, the subsequence ahahahahaha is suitable. In the third test case of the sample, the string ab has even length and is not laughter, so the answer is the letter 'a'. In the fifth test case of the sample, the letter 'y' is a consonant, and the whole string yay is laughter.

Recall that a subsequence is obtained from a string by deleting zero or more characters without changing the order of the remaining ones. A sequence $$$x$$$ is lexicographically smaller than a sequence $$$y$$$ if one of the following two conditions holds:

  • for some $$$i \geq 1$$$, the $$$i$$$-th character of $$$x$$$ comes earlier in the alphabet than the $$$i$$$-th character of $$$y$$$, and all characters before the $$$i$$$-th coincide in the two sequences;
  • $$$x$$$ is a prefix of $$$y$$$ and is not equal to $$$y$$$.