In information theory, the Hamming distance between two strings of equal length is the number of positions at which the corresponding symbols are different. In other words, it measures the minimum number of substitutions required to change one string into the other, or the minimum number of errors that could have transformed one string into the other.
$$$-$$$ Wikipedia
Assume that there are two strings with same length, which only contain lowercase characters, find a lexicographically smallest string with same length, and the Hamming distance between the target string and each original string are equal.
The first line contains a number $$$T$$$ ($$$1 \leq T \leq 100$$$), indicating the number of test cases.
Each time case contains two lines of strings, indicating the two original strings, which only contain lowercase characters. The length of string is smaller than $$$10^4$$$, and total length of the strings is less then $$$10^6$$$.
For each case, output Case $$$x$$$: $$$y$$$, in which x indicates the case number starting with 1, and y indicates the result of the target string. The target string should only contain lowercase characters.
2
abc
acd
abandon
newyork
Case 1: aaa
Case 2: aaaaark
Sample 2:
HM(abandon,aaaaark) = HM(newyork, aaaaark) = 5
And aaaaark is the lexicographically smallest string that meets the constraints.
Название |
---|