Insults

Insulting your friends and neighbors is the national sport of Ardenia. Like every sport, it has a set of rules that are hard to master even for the locals, let alone for tourists.

An insult is a word built entirely from the four vowels a, e, i, and o. Not every such word is an insult, though. The insults are exactly the words that can be produced by the following rules:

• The words ae and io are insults.
• If w1 and w2 are insults, then w1w2, aw1e, and iw1o are also insults.
• No other words are insults.

When someone insults you, you should fire back with a sharp reply. Linguists have found that the most fitting reply is always the insult of the same length that comes immediately after the given word in alphabetical order, where the letters are ordered a < e < i < o. For example, the best reply to aaeeio is aaeioe.

Some insults have no valid reply; these are called ultimate insults. For instance, ioioioio is an ultimate insult, because no insult of the same length comes after it alphabetically.

The first line contains an integer Z (1 ≤ Z ≤ 2000), the number of test cases.

Each of the next Z lines contains one test case: a non-empty string of length at most 1000000, consisting only of the letters a, e, i, and o.

For each test case, print a single line:

• If the string is not an insult, print INVALID.
• Otherwise, if the insult has a valid reply, print that reply — the insult of the same length that comes next in alphabetical order.
• If no such reply exists, print ULTIMATE.