Sonnets

Time limit2sMemory limit512 MB

Summary

For each poem, reduce every line to the vowel sequence after its last stressed syllable and label lines by first occurrence to build a rhyme scheme.

Level: Medium4 of 10
Topics: String, Hash map, Implementation, Simulation
Solved: No attempts yet

Problem

Shakespeare wrote more than 100 sonnets. What separates a sonnet from other poems is its rhyme scheme and its meter. Sonnets are usually written in iambic pentameter, and Shakespeare's sonnets are known for the rhyme scheme "ABAB CDCD EFEF GG": the first line rhymes with the third, the second with the fourth, the fifth with the seventh, and so on. This problem ignores the meter and looks only at the rhyme scheme.

You are given poems to analyze. To save you work, the syllable and stress structure is already marked. Syllables are separated by hyphens, and hyphens are used for nothing else. A stressed syllable is written in all capitals and every other syllable is written in all lowercase, even at the start of a sentence. English spelling does not tell you the pronunciation, so rhyming is simplified as follows. In each line, take the last stressed syllable together with the 0 or more unstressed syllables that follow it. Write down every vowel ('a', 'e', 'i', 'o', 'u', 'y') that appears in those syllables, in order. Two lines rhyme when this sequence of vowels is exactly the same for both of them.

The first line is labelled A, and so is every line that rhymes with it. The first line that does not rhyme with it is labelled B, and so is every line that rhymes with that one. Continue in the same way. An empty line becomes a single space in the rhyme scheme.

Input

The first line contains the number of data sets $K$ . Then $K$ data sets follow, each in the form below.

The first line of a data set contains the number of lines in the poem, $n$ ( $1 \le n \le 26$ ). The next $n$ lines hold the poem. Each of those lines consists of upper and lowercase letters, hyphens separating syllables, spaces separating words, and the punctuation marks '.', ',', ':', ';', which also separate words. Spaces and punctuation marks separate words, so they separate syllables too. Each syllable is at most 6 characters long and each line is at most 100 characters long. Every non-empty line has at least one stressed syllable.

Output

For each data set, print "Data Set x:" on a line of its own, where $x$ is the number of that data set. On the next line print the rhyme scheme. Print a blank line after each data set.

Examples2

Example 1

Input

1
9
you ARE the FAIR-est OF your SEX;
LET me BE your HE-ro.
I love YOU like ONE ov-er EX,
as EX app-ROA-ches ZE-ro.

WILL-i-am SHAKES saw a ME-te-or,
a ME-te-OR saw HE.
he RIGHT a-way SHOU-ted con-FI-te-or,
so FULL was HE of GLEE.

Expected output

Data Set 1:
ABAB CADE

Example 2

Input

3
4
the CAT sat
a HAT that
the MAT flat
a BAT at
5

the SUN is UP.
we RUN, we JUMP.
the MOON is LOW.

2
I SAID it TWICE.
you HEARD me NICE-ly.

Expected output

Data Set 1:
AAAA

Data Set 2:
 AAB 

Data Set 3:
AB