Under construction

Still being built. Things may change

Necklaces

Interview

Time limit1sMemory limit512 MB

Summary
Split each circular necklace string into runs of equal size and shade and report the longest and shortest run, preferring larger then lighter beads on ties.
Level

Easy3 of 10

Topics
Simulation, String
Solved
No attempts yet

Problem

Little Malgosia's passion is collecting necklaces made of assorted beads. Her collection has grown so large that she decided to catalog it. Each necklace is recorded as a string of English letters: consecutive letters correspond to consecutive beads, and the first and last beads are adjacent to each other (the necklace is a closed loop).

Malgosia sorts beads by size (small or large) and by shade (light or dark). She writes small beads with lowercase letters and large beads with uppercase letters. Light beads are the vowels a, e, i, o, u, y, and dark beads are the consonants.

She wants to split each necklace into the fewest possible segments (runs of consecutive beads), where every segment consists of beads of the same size and the same shade. Given only a necklace's description, she wants to determine its longest and its shortest segment. A necklace may contain several segments of maximum (or minimum) length; in that case she prefers the segment made of larger beads, or, if the tied segments share the same bead size, the segment made of lighter beads.

Help Malgosia: for each necklace, report the length and the bead type of the segment she is interested in.

Input

The first line contains an integer nn (1≤n≤201 \le n \le 20), the number of necklaces to inspect. Each of the next nn lines holds one necklace's description: a string of lowercase and uppercase English letters with no spaces.

Across a single test, the total length of all necklace strings does not exceed 1,000,000.

Output

For each necklace, print exactly two lines: the description of its longest segment, then the description of its shortest segment. When several segments tie for the extreme length, report the one with larger beads; if those segments also share the same bead size, report the lighter one.

Each description is an integer and a word separated by a single space: the number of beads in the segment and its type. The type is one of:

  • jasne for light, small beads,
  • JASNE for light, large beads,
  • ciemne for dark, small beads,
  • CIEMNE for dark, large beads.

Examples1

  1. Example 1

    Input
    2
oaBDrlIOIaeiy
oioioioi
    Expected output
    6 jasne
2 CIEMNE
8 jasne
8 jasne