DCEPC207 - Finally a Treat

no tags 

Anuja ma’am is getting more and more obsessed by her name (actually she loves it!!!). She has a strong belief that her name has something very special but she could not make it out what is it. As Vaibhav sir is very good in finding pattern he helped her with her problem, that she has a name in which only one character has maximum frequency i.e. ‘a’. She became very happy and decided to give a party to all of the members of DCE Coders who have special names. But wait, she finds out that the list is too big, so she decided to narrow it down. Here's how she narrows it: “Anuja ma’am will give a party to all those whose name is special and the character which makes their name special MUST be the character with maximum frequency in the entire list of names. There is only ONE special character in the string.”

As a student you are required to make a list of names ELLIGIBLE for party.

Remember, a name is special only if a SINGLE character has the maximum frequency in it. (See example #2 )

Input

1st line contains T(1<=T<=100), number of test cases. Next T lines contain a string(1<=Length of String<=10000) containing list of names separated by SPACES.

Output

Output k+1 lines for each test case, where k is the number of students ELLIGIBLE. First line contains “Case #x:” where x is the case number starting from 1. Then next k lines contain the names of ELLIGIBLE students.

Note: Each input string will have at least 1 word (of at least 1 character). i.e. there is no input string with only spaces

Example

Input:
2
abcdd abccd cccd
aabb aabcc aaa adaa Output: Case #1:
abccd
cccd
Case #2:
aaa
adaa

hide comments
Jared Deckard: 2012-03-06 19:28:19

@Kunal
It is a special WORD, but does it match the max freq char of the entire STRING?

Kunal Kapadia: 2012-03-06 07:49:28

why is abcdd not a special string in case #1.. it has only 1 character with max freq..

Adhityaa: 2012-03-02 05:20:17

I think so...

Rishi Mukherje: 2012-03-01 12:24:27

will it be wrong if print 'adaa' first and then 'aaa' for the 2nd one..?


Added by:dce coders
Date:2012-02-26
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Own Problem