You are given a string of uppercase English letters. You can highlight any number of the letters (possibly all or none of them). The highlighted letters do not need to be consecutive. Then, a new string is produced by processing the letters from left to right: non-highlighted letters are appended once to the new string, while highlighted letters are appended twice.
For example, if the initial string is HELLOWORLD
, you could highlight the H
, the first and last L
s and the last O
to obtain HHELLLOWOORLLD
. Similarly, if you highlight nothing, you obtain HELLOWORLD
, and if you highlight all of the letters, you obtain HHEELLLLOOWWOORRLLDD
. Notice how each occurrence of the same letter can be highlighted independently.
Given a string, there are multiple strings that can be obtained as a result of this process, depending on the highlighting choices. Among all of those strings, output the one that appears first in alphabetical (also known as lexicographical) order.
Note: A string appears before a different string in alphabetical order if is a prefix of or if at the first place and differ, the letter in is earlier in the alphabet than the letter in . For example, these strings are in alphabetical order: CODE
, HELLO
, HI
, HIM
, HOME
, JAM
.
Input Specification
The first line of the input gives the number of test cases, . test cases follow. Each test case is described in a single line containing a single string .
Output Specification
For each test case, output one line containing Case #x: y
, where is the test case number (starting from 1) and is the string that comes first alphabetically from the set of strings that can be produced from by the process described above.
Limits
Time limit: 2 seconds.
Memory limit: 1 GB.
.
Each character of is an uppercase letter from the English alphabet.
Test Set 1
.
Test Set 2
.
Sample Input
3
PEEL
AAAAAAAAAA
CODEJAMDAY
Sample Output
Case #1: PEEEEL
Case #2: AAAAAAAAAA
Case #3: CCODDEEJAAMDAAY
In Sample Case #1, these are all the strings that can be obtained, in alphabetical order:
PEEEEL
,
PEEEELL
,
PEEEL
,
PEEELL
,
PEEL
,
PEELL
,
PPEEEEL
,
PPEEEELL
,
PPEEEL
,
PPEEELL
,
PPEEL
, and
PPEELL
.
In Sample Case #2, every string that can be obtained contains only A
s. The
shortest of those is alphabetically first, because it is a prefix of all others.
In Sample Case #3, there are possible strings which can be generated from
CODEJAMDAY
out of which CCODDEEJAAMDAAY
is the lexicographically
smallest one.
Comments