욕설

친구와 이웃을 욕하는 것은 아르데니아의 국민 스포츠입니다. 모든 스포츠가 그렇듯 여기에도 규칙이 있는데, 원어민조차 익히기 어려울 정도라 관광객에게는 더욱 까다롭습니다.

욕설은 네 개의 모음 a, e, i, o 만으로 이루어진 단어입니다. 하지만 이 글자들로 이루어졌다고 해서 모두 욕설인 것은 아닙니다. 욕설은 다음 규칙으로 만들 수 있는 단어들뿐입니다.

• 단어 ae 와 io 는 욕설입니다.
• w1 과 w2 가 욕설이면 w1w2, aw1e, iw1o 도 욕설입니다.
• 이 방법으로 만들어지지 않는 단어는 욕설이 아닙니다.

누군가 당신을 욕하면 날카로운 대꾸를 준비하는 것이 좋습니다. 언어학자들에 따르면, 가장 알맞은 대꾸는 언제나 같은 길이를 가지면서 사전 순으로 바로 다음에 오는 욕설입니다. 이때 글자 순서는 a < e < i < o 입니다. 예를 들어 aaeeio 에 대한 가장 좋은 대꾸는 aaeioe 입니다.

어떤 욕설은 알맞은 대꾸가 존재하지 않는데, 이를 최종 욕설이라고 합니다. 예를 들어 ioioioio 는 같은 길이의 욕설 중 사전 순으로 그 뒤에 오는 것이 없으므로 최종 욕설입니다.

첫 줄에는 테스트 케이스의 개수를 나타내는 정수 Z (1 ≤ Z ≤ 2000) 가 주어집니다.

이어지는 Z 개의 줄에는 각각 하나의 테스트 케이스가 주어집니다. 각 줄은 a, e, i, o 로만 이루어진, 길이가 최대 1000000 인 비어 있지 않은 문자열입니다.

각 테스트 케이스마다 한 줄을 출력합니다.

• 문자열이 욕설이 아니면 INVALID 를 출력합니다.
• 욕설이고 알맞은 대꾸가 존재하면 그 대꾸(같은 길이이면서 사전 순으로 바로 다음에 오는 욕설)를 출력합니다.
• 알맞은 대꾸가 존재하지 않으면 ULTIMATE 를 출력합니다.