Smart Feature Phone 2

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$ ($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 $7 \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

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.