Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Smart Feature Phone 2

Limits: 5s, 512 MB

Alice worked in CIA. Right now he need to send an encrypted message to the headquarter(HQ) of CIA. As Alice is a lazy person and he wants to write the message using as less as possible effort. The only device he has to type is a configurable smart feature phone. As you are a programmer he wants you to configure the character of the key of the phone in a way that he needs minimum strokes to write the whole message. You can only change the position of the characters of buttons 2-9. After rearrangements count of characters in every button will be same.

Input

First line of the input is an integer value T<1000, total number of test case. Then for every case there will be a string in every line. Length of the string is less than 100000. String contains only lowercase letters.

Output

First line of the output is ‘Case X:’, where X is the number of test case. Then print a grid of size 7x15. Where you print the new keyboard layout. If there is multiple solution exists, print the solution which gives the lexicographically smallest string when characters are concatenated in orders of key of 2-9

Samples

InputOutput
2
abcd
abcdefghi
Case 1:
###############
#....#aef#bgh.#
###############
#cij.#dkl#mno.#
###############
#pqrs#tuv#wxyz#
###############
Case 2:
###############
#....#abj#ckl.#
###############
#dmn.#eop#fqr.#
###############
#gstu#hvw#ixyz#
###############

Input file is huge. Use faster IO.

Author
Discussion
Submit

Login to submit