题目描述

Cameron and Jamie are about to welcome a second baby into their lives. They are already good at working together as parents, but right now they are disagreeing about one crucial thing! Cameron wants to name the baby one name (the string $\mathbf{C}$), whereas Jamie wants to name the baby something else (the string $\mathbf{J}$).

You want to help them find a compromise name that is as close as possible to what each of them wants. You think you can do this using the notion of edit distance. The edit distance between two strings $S_1$ and $S_2$ is the minimum number of operations required to transform $S_1$ into $S_2$, where the allowed operations are as follows:

• Insert one character anywhere in the string.
• Delete one character from anywhere in the string.
• Change one character in the string to any other character.

For example, the edit distance between CAMERON and JAMIE is 5. One way to accomplish the transformation in 5 steps is the following: CAMERON to JAMERON (change) to JAMIERON (insert) to JAMIEON (delete) to JAMIEN (delete) to JAMIE (delete). Any transformation from CAMERON into JAMIE requires at least this many operations.

To make the compromise name $N$ as close as possible to the original desires of the parents, you want $N$ to be a non-empty string such that the sum of the edit distances between $\mathbf{C}$ and $N$ and between $\mathbf{J}$ and $N$ is as small as possible. Out of all those choices for $N$, to make sure the compromise is fair, you must choose an $N$ such that the difference between those two edit distances is also as small as possible. Please find a compromise name for Cameron and Jamie.

输入格式

The first line of the input gives the number of test cases, $\mathbf{T}$. $\mathbf{T}$ test cases follow. Each case consists of a single line with two strings $\mathbf{C}$ and $\mathbf{J}$: the names that Cameron and Jamie have proposed for the baby, respectively. Each of these names is made up of uppercase English alphabet letters.

输出格式

For each test case, output one line containing Case #x: y, where $x$ is the test case number (starting from 1) and $y$ is a name that meets the requirements mentioned in the statement. Note that $y$ must contain only uppercase English letters.

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

提示

Sample Explanation

Sample Test Set 1 meets the limits for Test Set 1. Another sample case that does not meet those limits but could appear in Test Set 2.

The above cases meet the limits for Test Set 1. Another sample case that does not meet those limits appears at the end of this section.

In Sample Case #1, the edit distance from XYZZY to ZZY is 2 (delete the first two letters), and the edit distance from ZZYZX to ZZY is 2 (delete the last two letters). XZZX and ZYYZY would also work. No possible name has a sum of edit distances that is less than 4.

ZY, for example, has the same edit distance to C as to J (3, in each case). However the sum of those distances would be 6, which is not minimal, so it would not be an acceptable answer.

XZZY is also unacceptable. Its edit distances to C and J, respectively, are 1 and 3. The sum of those edit distances is minimal, but the difference between the two ($|1-3| = 2$) is not minimal, since we have shown that it is possible to achieve a difference of 0.

In Sample Case #2, Y and Z are the only acceptable answers.

In Sample Case #3, notice that input length restrictions do not apply to the output, so the shown answer is acceptable in either test set. Another possible answer is YYXXY.

In Sample Case #4, the edit distance between XZXZXZ and ZYZX is 3, and the edit distance between YZ and ZYZX is 2. The sum of those edit distances is 5, and their difference is 1; these values are optimal for this case.

Limits

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

Test Set 1 (4 Pts, Visible Verdict)

• $1 \leq \text{length of } \mathbf{C} \leq 6$.
• $1 \leq \text{length of } \mathbf{J} \leq 6$.
• The i-th letter of $\mathbf{C}$ is an uppercase x, y, or z, for all i.
• The i-th letter of $\mathbf{J}$ is an uppercase x, y, or z, for all i.

Test Set 2 (8 Pts, Hidden Verdict)

• $1 \leq \text{length of } \mathbf{C} \leq 60$.
• $1 \leq \text{length of } \mathbf{J} \leq 60$.
• The $i$-th letter of $\mathbf{C}$ is an uppercase English alphabet letter, for all i.
• The $i$-th letter of $\mathbf{J}$ is an uppercase English alphabet letter, for all i.