It is quite simple really: I'll give you a list of words and you use them to make a crossword puzzle in a 16x32 grid. You'll be able to use the words more than once in the grid and there is a special "flipper" square you can use as a wild card. The winner will be the program that can create the "best" fully connected crossword in one minute. The original problem appeared here: Programmer of the month contest (Feb. 2005).

The Starting Grid
- The grid will consist of 32 columns and 16 rows

The Word List
- There will be at least one word and fewer than 512 words in the wordlist
- Each word will be two letters long or more (WORDLENGTH >= 2)
- Each word will be sixteen letters long or less (WORDLENGTH <= 16)
- Words in the wordlist will contain only letters "A" through "Z" in upper case letters with no white space
- Words will appear in the wordlist with one word per line
- Words will not be repeated in the wordlist, but they may be used multiple times in your solution
- Do not assume anything (like sorting) about arrangement of the words in the list
- Do not assume anything about whether a "word" is contained in any dictionary: POTM, ABCDEFG, and XYZZY are all possible "words"
- Words in the list may be subsets of one another: SCAT, CAT, CATS and XCATS may all appear in the same wordlist ... there is no bonus for using words containing other words ... see scoring note below
- There may be words in the wordlist which are not possible to connect to any other words in the wordlist

Placement of the Words onto the Grid
- Any word from the word list may be used in your solution as many times as you wish
- You may use any subset of words in the wordlist, or all of them
- All words placed on the grid must read left-to-right or downwards
- All words placed on the grid must be connected to one another
- ONLY words on the wordlist may be used and empty squares or grid boundaries must be used immediately before and after all words
- Words may not "wrap-around" the grid boundaries in any sense
- Your solution does not need to be symmetric in any sense
- Output which is not connected, or contains words which do not appear in the wordlist, will receive a score of zero

The Flipper Square
- There is one (and only one) "flipper" square (denoted by an asterisk) permitted in your output
- You may place the flipper square within any word you place on the grid
- When used, it may represent a different letter in the horizontal and vertical words of which it is a part
- Any words formed using the "flipper" square must be part of the wordlist (if C*T is placed on the grid, then there must be a three letter word in the wordlist that begins with "C" and ends in "T")
- The "flipper" will likely be used at a word intersection, although this is not required (why would you use it elsewhere??)

Input

t – number of test cases [t <= 10]
N - number of words for given test case, then N lines follows each line contain one word, in upper case. Word will contain no whitespace or characters other than [A-Z].

Output

For each testcase your output must contain exactly 16 lines with 32 characters followed by a line feed as in printf("\n") on each line. The letters in your output must be upper case [A-Z} as in the wordlist. The "Flipper" (if used) in your output should be an asterisk "*". Squares that do not contain a letter or a flipper should contain an underbar "_". There should be no white space in your output. Your output must be exactly t*528 bytes.

Score

Your "SCORE" will be the total number of letters in all the words used in your solution. If a word is contained within a longer word, only the longer word will contribute to the score ... for example, using POTM would not score for the word POT even if both are in the wordlist. The "flipper" square contributes to the word length as though it was a part of each word. The total score will be the sum of scores for individual test cases.

Example

Input:
1
28
NECESSARY
POLITICAL
CONNECTED
SEPARATE
OPINIONS
REQUIRES
SEPARATION
SELFEVIDENT
UNALIENABLE
HAPPINESS
GOVERNMENTS
INSTITUTED
DERIVING
GOVERNMENT
DESTRUCTIVE
INSTITUTE
FOUNDATION
PRINCIPLES
ORGANIZING
ESTABLISHED
TRANSIENT
ACCORDINGLY
EXPERIENCE
SUFFERABLE
THEMSELVES
ABOLISHING
ACCUSTOMED
USURPATIONS

Output:
CONNECTED__USURPATIONS_CONNECTED
O_E___R___R_U____R_P___O_E___R__
NECESSARY_E_FOUNDATION_NECESSARY
N_E___N___Q_F____N_N___N_E_U_N__
E_S_INSTITUTED_INSTITUTE_S_F_S__
C_S_N_I___I_R____I_O___C_S_F_I_E
TRANSIENT_R_A_GOVERNMENT_A_E_E_S
E_R_T_N_H_E_B____N_S_X_E_R_R_N_T
D_Y_I_THEMSELVES_T___P_D_Y_A_T_A
____T___M___E__E_____E_____B___B
HAPP*NESS______P____PRINCIPLES_L
____T___E_SEPARATION_I_____E___I
SUFFERABLE_____R_____E_________S
____D___V_SEPARATION_NECESSARY_H
________E______T_____C_________E
HAPPINESS_THEMSELVES_ESTABLISHED

Score:
341