P13053 [GCJ 2020 #1A] Pattern Matching

Many terminals use asterisks (`*`) to signify "any string", including the empty string. For example, when listing files matching `BASH*`, a terminal may list BASH, BASHER and BASHFUL. For `*FUL`, it may list BEAUTIFUL, AWFUL and BASHFUL. When listing `B*L`, BASHFUL, BEAUTIFUL and BULL may be listed. In this problem, formally, a pattern is a string consisting of only uppercase English letters and asterisks (`*`), and a name is a string consisting of only uppercase English letters. A pattern $p$ matches a name $m$ if there is a way of replacing every asterisk in $p$ with a (possibly empty) string to obtain $m$. Notice that each asterisk may be replaced by a different string. Given $\mathrm{N}$ patterns, can you find a single name of at most $10^{4}$ letters that matches all those patterns at once, or report that it cannot be done?

The first line of the input gives the number of test cases, $\mathrm{T}$. $\mathrm{T}$ test cases follow. Each test case starts with a line with a single integer $\mathrm{N}$: the number of patterns to simultaneously match. Then, $\mathrm{N}$ lines follow, each one containing a single string $\mathrm{P}_{\mathrm{i}}$ representing the $\mathrm{i}$-th pattern.

For each test case, output one line containing `Case #x: y`, where $\mathrm{x}$ is the test case number (starting from 1) and $\mathrm{y}$ is any name containing at most $10^{4}$ letters such that each $\mathrm{P}_{\mathrm{i}}$ matches $\mathrm{y}$ according to the definition above, or `*` (i.e., just an asterisk) if there is no such name.

**Sample Explanation** In Sample Case #1, there are other possible answers, including COCOCONUTS and ILIKECOCONUTS. Neither COCONUTSAREGREAT nor COCOANUTS would be acceptable. Notice that the same pattern may appear more than once within a test case. In Sample Case #2, there is no acceptable name, so the answer is `*`. The following cases could not appear in Test Set 1, but could appear in Test Set 2 or Test Set 3: ``` 4 H*O HELLO* *HELLO HE* ``` HELLO and HELLOGOODBYEHELLO are examples of acceptable answers. OTHELLO and HELLOO would not be acceptable. ``` 2 CO*DE J*AM ``` There is no name that matches both patterns, so the answer would be `*`. ``` 2 CODE* *JAM ``` CODEJAM is one example of an acceptable answer. The following cases could not appear in Test Set 1 or Test Set 2, but could appear in Test Set 3: ``` 2 A*C*E *B*D* ``` ABCDE and ABUNDANCE are among the possible acceptable answers, but BOLDFACE is not. ``` 2 A*C*E *B*D ``` There is no name that matches both patterns, so the answer would be `*`. **Limits** - $1 \leqslant \mathrm{T} \leqslant 100$. - $2 \leqslant \mathrm{N} \leqslant 50$. - $2 \leqslant$ length of $\mathrm{P}_{\mathrm{i}} \leqslant 100$, for all $\mathrm{i}$. - Each character of $\mathrm{P}_{\mathrm{i}}$ is either an uppercase English letter or an asterisk (*), for all $\mathrm{i}$. - At least one character of $\mathrm{P}_{\mathrm{i}}$ is an uppercase English letter, for all $\mathrm{i}$. **Test set 1 (5 Pts, Visible Verdict)** - Exactly one character of $\mathrm{P}_{\mathrm{i}}$ is an asterisk (*), for all $\mathrm{i}$. - The leftmost character of $\mathrm{P}_{\mathrm{i}}$ is the only asterisk (*), for all $\mathrm{i}$. **Test set 2 (5 Pts, Visible Verdict)** - Exactly one character of $\mathrm{P}_{\mathrm{i}}$ is an asterisk (*), for all $\mathrm{i}$. **Test set 3 (18 Pts, Visible Verdict)** - At least one character of $\mathrm{P}_{\mathrm{i}}$ is an asterisk (*), for all $\mathrm{i}$.