Under construction

Still being built. Things may change

Rune

Interview

Time limit1sMemory limit512 MB

Summary
For each language, compute each rune's power as the number of maximal runs of consecutive vowels, then sort by power descending and by name ascending.
Level

Easy3 of 10

Topics
Sorting, String, Implementation, Brute force
Solved
No attempts yet

Problem

Akara is a great wizard of Sanctuary. She is interested in runes, the letters of an ancient language that strengthen magic items and spells. Her recent studies show that some runes are more powerful than others.

Runes from the Anglo-Saxon language.

The power of a rune is the number of vowels (a, e, i, o, u) in its name, except that a group of adjacent vowels counts only once. For example:

  1. The rune named 'gattaca' has power 3, because its name holds 3 vowels and none of them are adjacent.
  2. The rune named 'beautiful' also has power 3. Its name holds 5 vowels, but 'eau' is a group of adjacent vowels and counts as one.

Each language has its own runes and runes of different languages are never mixed. Akara wants to rank the runes she knows in each language so she can find them later. Your task, as her apprentice, is to read the rune list of each language and print its runes from the most powerful to the least powerful. Runes of equal power are printed in lexicographical order.

Input

The first line contains LL, the number of languages Akara is interested in. (1<L≤101 < L \le 10)

Each of the next LL lines starts with NN, the number of runes in that language (1<N≤1051 < N \le 10^5), followed by NN space separated strings WW, one for each rune. Every string WW consists of lowercase English letters (a-z) only and its length is at most 100.

Output

Print LL lines. Each line contains the NN runes of one language, separated by a single space. Print the more powerful runes first, and order runes of equal power lexicographically.

Examples3

  1. Example 1

    Input
    2
    2 gattaca beautiful
    7 aem un ogla ulk ohm zaradar ng
    
    Expected output
    beautiful gattaca
    zaradar ogla aem ohm ulk un ng
    
  2. Example 2

    Input
    2
    2 zz ng
    2 mm bcd
    
    Expected output
    ng zz
    bcd mm
    
  3. Example 3

    Input
    2
    4 aaaaaaaaaa aeiou ababab a
    4 oo o boo book
    
    Expected output
    ababab a aaaaaaaaaa aeiou
    boo book o oo