I :: Insults

Time Limit: 3 Seconds    Memory Limit: 131072 KB

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 i w₁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).

Input

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 below.

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.

Output

For each test case, your program has to write an output conforming to the format described below.

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.

Sample Input

3 
eaeeio 
aaeeio 
ioioioioio

Sample Output

INVALID 
aaeioe 
ULTIMATE

Submit

Source: Central European Regional Contest 2010