侮辱你的朋友和邻居是阿德尼亚（Ardenia）的国民运动。然而，就像每项运动一样，它有一套相当难以掌握的规则，即使是当地人也难以完全学会，更不用说游客了。

首先，侮辱语是仅由四个元音字母 a、e、i 和 o 组成的单词。但并非所有由这些字母组成的单词都是侮辱语。仅有的两个双字母侮辱语是 ae 和 io。如果单词 $w_1$ 和 $w_2$ 是侮辱语，那么单词 $w_1w_2$、$aw_1e$ 和 $iw_1o$ 也是侮辱语。侮辱语只能通过这种方式创建。

通常，如果有人侮辱你，你最好准备一个尖锐的回敬侮辱语。显然，大多数回答都是不合适的。例如，如果你听到 aaeeio（意思是“你打起架来像个养奶牛的农夫”），你不应该用 aeio（“你是个傻瓜”）来回应。让所有人惊讶的是，语言学家发现，在所有情况下，最合适的回敬是长度相同且在字典序中紧随其后的侮辱语。因此，对于上述侮辱语，最好的回敬将是 aaeioe（“真合适；你打起架来像只母牛”）。这一规则也意味着存在所谓的“终极侮辱语”，即那些没有合适回敬的侮辱语。八个字母的终极侮辱语是 ioioioio（“你妈是个仓鼠，你爸闻起来像接骨木果”）。

输入格式

输入包含多个测试用例。

第一行包含一个正整数 $Z \le 2000$，表示测试用例的数量。

接下来是 $Z$ 个测试用例，每个测试用例占一行，包含一个长度最多为 $10^6$ 的字符串。字符串中只会出现字母 a、e、i 和 o。

输出格式

对于每个测试用例，输出一行：

• 如果该字符串不是一个合法的侮辱语，输出 INVALID。
• 否则，输出对读入的侮辱语的最佳回敬；如果不存在这样的回敬，则输出 ULTIMATE。

样例

输入样例 1

3
eaeeio
aaeeio
ioioioioio

输出样例 1

INVALID
aaeioe
ULTIMATE