Description

Cameron 和 Jamie 即将迎来他们的第二个孩子。他们在育儿方面已经配合得很好了，但此刻却在一个关键问题上产生了分歧！Cameron 想给孩子取名为 $\mathbf{C}$，而 Jamie 则想取名为 $\mathbf{J}$。

你希望帮助他们找到一个折中的名字，使其尽可能接近双方的想法。你认为可以通过编辑距离的概念来实现这一点。两个字符串 $S_1$ 和 $S_2$ 之间的编辑距离是指将 $S_1$ 转换为 $S_2$ 所需的最少操作次数，允许的操作包括：

• 在字符串任意位置插入一个字符。
• 删除字符串中的任意一个字符。
• 将字符串中的一个字符替换为其他任意字符。

例如，CAMERON 和 JAMIE 之间的编辑距离为 5。一种用 5 步完成转换的方式如下：CAMERON → JAMERON（替换）→ JAMIERON（插入）→ JAMIEON（删除）→ JAMIEN（删除）→ JAMIE（删除）。从 CAMERON 转换到 JAMIE 至少需要这么多操作。

为了使折中名字 $N$ 尽可能接近父母的原始意愿，你需要选择一个非空字符串 $N$，使得 $\mathbf{C}$ 与 $N$ 的编辑距离和 $\mathbf{J}$ 与 $N$ 的编辑距离之和最小。在所有满足这一条件的 $N$ 中，为了确保公平性，你还必须选择一个使得这两个编辑距离之差也尽可能小的 $N$。请为 Cameron 和 Jamie 找到一个折中名字。

Input Format

输入的第一行包含测试用例的数量 $\mathbf{T}$。随后是 $\mathbf{T}$ 个测试用例。每个测试用例包含一行，其中有两个字符串 $\mathbf{C}$ 和 $\mathbf{J}$，分别表示 Cameron 和 Jamie 提议的婴儿名字。这些名字均由大写英文字母组成。

Output Format

对于每个测试用例，输出一行 Case #x: y，其中 $x$ 是测试用例编号（从 1 开始），$y$ 是满足题目要求的名字。注意，$y$ 必须仅包含大写英文字母。

4
XYZZY ZZYZX
Y Z
YYXXYZ ZYYXXY
XZXZXZ YZ

Case #1: ZZY
Case #2: Z
Case #3: ZYYXXYZ
Case #4: ZYZX

1
GCJ ABC

Case #1: GC

Hint

样例解释

样例测试集 1 符合测试集 1 的限制。另一个不符合这些限制但可能出现在测试集 2 中的样例见下文。

在样例 #1 中，从 XYZZY 到 ZZY 的编辑距离为 2（删除前两个字母），从 ZZYZX 到 ZZY 的编辑距离为 2（删除最后两个字母）。XZZX 和 ZYYZY 也是可行的解。没有其他名字能使编辑距离之和小于 4。

例如，ZY 到 C 和 J 的编辑距离相同（均为 3），但编辑距离之和为 6，并非最小值，因此不是可接受的答案。

XZZY 也不符合要求。它到 C 和 J 的编辑距离分别为 1 和 3。虽然编辑距离之和是最小的，但两者之差（$|1-3| = 2$）并非最小，因为我们已经证明可以找到差值为 0 的解。

在样例 #2 中，Y 和 Z 是唯一可接受的答案。

在样例 #3 中，注意输入的长度限制不适用于输出，因此所示答案在任一测试集中均可接受。另一个可能的答案是 YYXXY。

在样例 #4 中，XZXZXZ 到 ZYZX 的编辑距离为 3，YZ 到 ZYZX 的编辑距离为 2。编辑距离之和为 5，差值为 1；这些值是该情况下的最优解。

数据范围

• $1 \leq T \leq 100$。
• $\mathbf{C} \neq \mathbf{J}$。

测试集 1（4 分，可见判定）

• $1 \leq \text{C 的长度} \leq 6$。
• $1 \leq \text{J 的长度} \leq 6$。
• $\mathbf{C}$ 的第 $i$ 个字母是大写 X、Y 或 Z。
• $\mathbf{J}$ 的第 $i$ 个字母是大写 X、Y 或 Z。

测试集 2（8 分，隐藏判定）

• $1 \leq \text{C 的长度} \leq 60$。
• $1 \leq \text{J 的长度} \leq 60$。
• $\mathbf{C}$ 的第 $i$ 个字母是大写英文字母。
• $\mathbf{J}$ 的第 $i$ 个字母是大写英文字母。

翻译由 DeepSeek V3 完成