Description

许多终端使用星号(*)表示"任意字符串"，包括空字符串。例如，当列出匹配BASH*的文件时，终端可能显示 BASH、BASHER 和 BASHFUL。对于*FUL，可能显示 BEAUTIFUL、AWFUL 和 BASHFUL。当列出B*L时，可能显示 BASHFUL、BEAUTIFUL 和 BULL。

在本题中，模式是仅由大写字母和星号(*)组成的字符串，名称是仅由大写字母组成的字符串。若模式 $p$ 能通过将每个星号替换为任意字符串（可为空）得到名称 $m$，则称 $p$ 匹配 $m$。注意不同星号可被替换为不同字符串。

给定 $\mathrm{N}$ 个模式，请构造一个长度不超过 $10^{4}$ 的字符串，使其同时匹配所有给定模式；若不存在这样的字符串，则报告无解。

Input Format

输入第一行包含测试用例数 $\mathrm{T}$。随后每个测试用例包含：

• 第一行：整数 $\mathrm{N}$ 表示模式数量
• 随后 $\mathrm{N}$ 行：每行一个字符串 $\mathrm{P}_{\mathrm{i}}$ 表示第 $\mathrm{i}$ 个模式

Output Format

对于每个测试用例，输出一行 Case #x: y，其中：

• $x$ 为测试用例编号（从 1 开始）
• $y$ 为满足条件的长度不超过 $10^{4}$ 的字符串，若无解则输出 *

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

Case #1: COCONUTS
Case #2: *

Hint

样例 #1 中，其他可行解包括 COCOCONUTS 和 ILIKECOCONUTS，但 COCONUTSAREGREAT 和 COCOANUTS 不符合要求。注意同一模式可能在测试用例中重复出现。

样例 #2 无解，故输出 *。

以下情况不会出现在测试集 1，但可能出现在测试集 2 或 3：

  4
  H*O
  HELLO*
  *HELLO
  HE*

可行解包括 HELLO 和 HELLOGOODBYEHELLO，但 OTHELLO 和 HELLOO 不符合。

  2
  CO*DE
  J*AM

无解，输出 *。

  2
  CODE*
  *JAM

CODEJAM 是可行解之一。

以下情况仅可能出现在测试集 3：

  2
  A*C*E
  *B*D*

可行解包括 ABCDE 和 ABUNDANCE，但 BOLDFACE 不符合。

  2
  A*C*E
  *B*D

无解，输出 *。

数据范围

• $1 \leqslant \mathrm{T} \leqslant 100$
• $2 \leqslant \mathrm{N} \leqslant 50$
• $2 \leqslant \mathrm{P}_{\mathrm{i}}$ 长度 $\leqslant 100$
• 每个 $\mathrm{P}_{\mathrm{i}}$ 仅含大写字母和星号
• 每个 $\mathrm{P}_{\mathrm{i}}$ 至少包含一个大写字母

测试集 1（5 分，可见判果）

• 每个 $\mathrm{P}_{\mathrm{i}}$ 仅含一个星号
• 星号必须位于模式开头

测试集 2（5 分，可见判果）

• 每个 $\mathrm{P}_{\mathrm{i}}$ 仅含一个星号

测试集 3（18 分，可见判果）

• 每个 $\mathrm{P}_{\mathrm{i}}$ 至少含一个星号

翻译由 DeepSeek V3 完成