SP9967 PWORDS - Playing with Words

Amr M. 是一个深信阴谋论的人。他对各类事物抱有强烈的怀疑态度，特别是那些电视广告，总认为其中隐藏着不为人知的秘密。最近，他对那些由两个词组成的广告尤其关注：即 ad1 和 ad2，怀疑它们暗藏玄机。 通过秘密渠道，Amr 掌握到了一些信息，揭示了广告中隐藏信息的方式。通常，这些信息由两个原始字符串 orig1 和 orig2 组成，并通过以下步骤进行转换： 1. 将 orig1 中的字母随机打乱。 2. 将 orig2 中的字母随机打乱。 3. 在 orig1 或 orig2 中挑选一个字母，用字母表中紧邻的字母进行替换（可以是前一个或者后一个字母）。 经过这样的转换，orig1 和 orig2 就变为了广告中的 ad1 和 ad2。例如，orig1 = "bcd"，orig2 = "wcy" 时，可能会生成 ad1 = "dcb" 和 ad2 = "cxy"（先打乱为 cwy，然后将 'w' 替换为 'x'）。 经过更深入的研究，Amr 还发现了一个称为距离 X 的指标，它等于 orig1 和 ad1 之间的距离加上 orig2 和 ad2 之间的距离。两个字符串之间的距离定义为相同位置上字母的绝对差值之和（例如，difference("ab", "cd") = abs('a' - 'c') + abs('b' - 'd') = 4）。 然而，可能的原始字符串组合数量非常大，所以 Amr 希望你能帮忙计算。给定广告字符串 ad1 和 ad2，以及距离 X = distance(orig1, ad1) + distance(orig2, ad2)，你需要返回可能的原始字符串 orig1 和 orig2 的总数。

第一行是一个整数 T，表示测试用例的数量。接下来的 T 行中，每行包含三个部分：ad1、ad2 和 X，用空格隔开。其中 ad1 和 ad2 是由小写字母组成的字符串。

对每个测试用例，输出一行，格式为 **“Case K: cnt”**，其中 K 是测试用例的序号，cnt 是可能的 orig1 和 orig2 的组合数量。 ## 示例输入 ``` 2 c n 1 kbenh kbenh 5 ``` ## 示例输出 ``` Case 1: 4 Case 2: 16 ```

- 1 ≤ T ≤ 100 - 1 ≤ |ad1|, |ad2| ≤ 10 - 0 ≤ X ≤ 100 **本翻译由 AI 自动生成**