3434번 - Insults 다국어

Insulting your friends and neighbors is the Ardenia national sport. However, as every sport, it has a certain set of rules which are quite hard to learn even by natives, not to mention the tourists. First of all, the insults are single words consisting entirely of four vowels: a, e, i, and o. But not all words that consist of these letters are insults. The only two letter insults are ae and io. If words w₁ and w₂ are insults, then words w₁w₂ and aw₁e and iw₁o are insults as well. Insults are created only in such way.

Usually, if somebody is insulting you, then you better have a sharp response insult prepared. Obviously, most of the answers are inappropriate. For example if you hear aaeeio (meaning you fight like a dairy farmer) you should not reply with aeio (you are stupid). To everybody’s surprise, the linguists have found out that in all the cases the most appropriate reply is the insult of the same length and alphabetically next. Thus, for the insult above, the best reply would be aaeioe (how appropriate; you fight like a cow). This rule implies also the existence of so called ultimate insults, i.e., the ones for which there is no good reply. The eight letter ultimate insult is ioioioio (your mother was a hamster and your father smelt of elderberries).

The input contains several test cases. The first line of the input contains a positive integer Z ≤ 2000, denoting the number of test cases. Then Z test cases follow, each conforming to the format described in section Input. For each test case, your program has to write an output conforming to the format described in section Output.

The input instance is one line containing a string of length at most 10⁶. The only letters occurring in the string will be a, e, i and o.

You should output a single line containing the word INVALID if the string is not an insult. Otherwise, you should output the best reply to the insult read or word ULTIMATE if no such reply exists.