Pattern Matching

Many terminals use asterisks (*) to mean "any string", including the empty string. For example, when listing files that match BASH*, a terminal may list BASH, BASHER, and BASHFUL. For *FUL, it may list BEAUTIFUL, AWFUL, and BASHFUL. For B*L, it may list BASHFUL, BEAUTIFUL, and BULL.

A pattern is a string made only of uppercase English letters and asterisks. A name is a string made only of uppercase English letters. A pattern p matches a name m if every asterisk in p can be replaced with a possibly empty string so that the result is m. Each asterisk may be replaced by a different string.

Given N patterns, find one name of at most 10^4 letters that matches all of them at once, or report that no such name exists.

The first line contains T, the number of test cases. Each test case starts with a line containing N, the number of patterns. The next N lines each contain one pattern Pi. The same pattern may appear more than once.

For each test case, print Case #x: y, where x is the test case number starting from 1. Print any name y of at most 10^4 letters that matches every Pi. If no such name exists, print *.

1 <= T <= 100

2 <= N <= 50

2 <= length of Pi <= 100

Each character of Pi is an uppercase English letter or an asterisk.

Each Pi contains at least one uppercase English letter.

In Sample Case 1, other valid answers include COCOCONUTS and ILIKECOCONUTS. COCONUTSAREGREAT and COCOANUTS are not valid.

In Sample Case 2, no valid name exists, so the answer is *.

Patterns H*O, HELLO*, *HELLO, and HE* can be matched by HELLO or HELLOGOODBYEHELLO. OTHELLO and HELLOO are not valid.

Patterns CO*DE and J*AM have no common name, so the answer is *.

Patterns CODE* and *JAM can be matched by CODEJAM.

Patterns A*C*E and *B*D* can be matched by ABCDE or ABUNDANCE, but BOLDFACE is not valid.

Patterns A*C*E and *B*D have no common name, so the answer is *.

Patterns **Q** and *A* can be matched by QUAIL or AQ.