Smart Feature Phone 2

maruf_0011 AB Bank IUT 8th ICT Fest...
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 TT (T<1000T<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 XX is the number of test case. Then print a grid of size 7×157 \times 15. 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.

Sample

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.

Submit

Login to submit.

Statistics

56% Solution Ratio
iutictf8.33$wRMnHEarliest, Nov '16
iutictf8.36$p0MrVFastest, 207692.2s
iutictf8.33$wRMnHLightest, 262 kB
KnightMareShortest, 1870B
Toph uses cookies. By continuing you agree to our Cookie Policy.