Wiping Words

Time limit1sMemory limit128 MB

Summary

Repeatedly blank out any word whose column has no support in the next line, or that appears in the last line, until no more words can be wiped.

Level: Medium7 of 10
Topics: Simulation, Implementation, String matching
Solved: No attempts yet

Problem

You are given a paragraph of text as a sequence of lines. Within a line, a word is a maximal run of English letters (a–z, A–Z); words are separated by blanks or asterisks (*).

A word is wiped out when either of the following holds:

for every column occupied by the word, the character in the same column of the next line is neither a letter nor an asterisk (it is a blank, or the next line does not extend that far), or
the word occurs in the last line of the paragraph.

When a word is wiped out, every occurrence of that exact word in the whole paragraph is replaced by blanks, regardless of what lies in the next line beneath those occurrences. Asterisks and blanks never disappear, and words are case-sensitive (so Cat and cat are different words).

Wiping a word turns its letters into blanks, which can remove the support beneath words in the line above and cause further words to be wiped out. Keep applying the rule until no more words can be wiped out.

Input

The first line contains an integer $t$ ( $1 \le t \le 20$ ), the number of test cases.

Each test case is a sequence of lines made up of the characters A–Z, a–z, blanks, and asterisks (*). Each test case is terminated by a line containing a single # character, which is not part of the paragraph.

Output

For each test case, output the paragraph after all possible words have been wiped out, with wiped letters shown as blanks. Trailing whitespace at the end of a line is ignored when your output is judged. After the lines of each test case, print a line containing a single # character.

Examples3

Example 1

Input

2
ACM is
**
#
in this world
you are in*side
the world
*
#

Expected output

ACM
**
#

you       *
the
*
#

Example 2
Input
```
1
cat
*
#
```
Expected output
```
cat
*
#
```
Example 3
Input
```
1
go home now
*   *
#
```
Expected output
```
go home
*   *
#
```