题目描述

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.

2
5
*CONUTS
*COCONUTS
*OCONUTS
*CONUTS
*S
2
*XZ
*XYZ

Case #1: COCONUTS
Case #2: *

提示

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}$.