题目描述

Ayla 有两个字符串 $A$ 和 $B$，长度均为 $L$，每个字符串均由大写英文字母组成。她想知道 $A$ 中有多少个不同的子串，可以作为 $B$ 的某个异序词子串出现。更正式地说，她想要统计不同的有序对 $(i, j)$ 的数量，其中 $0 \le i \le j < L$，使得 $A$ 中从第 $i$ 个字符到第 $j$ 个字符（包含两端）构成的字符多重集与 $B$ 中某个长度为 $(j - i + 1)$ 的连续子串的字符多重集相同。

输入格式

输入的第一行给出测试用例的数量 $T$。接下来有 $T$ 个测试用例。每个测试用例的第一行包含一个整数 $L$，表示字符串的长度。随后两行各包含一个长度为 $L$ 的字符串，依次为字符串 $A$ 和 $B$。

输出格式

对于每个测试用例，输出一行，格式为 Case #x: y，其中 $x$ 是测试用例编号（从 $1$ 开始），$y$ 是 Ayla 所求的答案，如上所述。

6
3
ABB
BAB
3
BAB
ABB
6
CATYYY
XXXTAC
9
SUBXXXXXX
SUBBUSUSB
4
AAAA
AAAA
19
PLEASEHELPIMTRAPPED
INAKICKSTARTFACTORY

Case #1: 5
Case #2: 6
Case #3: 6
Case #4: 6
Case #5: 10
Case #6: 9

提示

在样例 #1 中，$L = 3$，$A = \text{ABB}$，$B = \text{BAB}$。$A$ 共有 $6$ 个子串：

• A：子串 A 在 $B$ 中（平凡地）是一个异序词。
• B：子串 B 在 $B$ 中（平凡地）是一个异序词。
• B：子串 B 在 $B$ 中（平凡地）是一个异序词。
• AB：子串 AB 在 $B$ 中（平凡地）是一个异序词。
• BB：在 $B$ 中不存在对应的异序词子串。
• ABB：子串 BAB 在 $B$ 中是一个异序词。

总共有 $5$ 个子串在 $B$ 中存在对应的异序词子串，因此答案为 $5$。

在样例 #2 中，注意它与样例 #1 相同，只是交换了 $A$ 和 $B$。这导致答案变为 $6$！

在样例 #3 中，注意 $A$ 中的子串 CAT 在 $B$ 中有对应的异序词子串 TAC。即使这两个子串在各自的字符串中位于不同位置，该子串仍然被计入。

在样例 #4 中，注意尽管 $A$ 中的子串 SUB 在 $B$ 中有多个对应的异序词子串，但它只被计数一次。

在样例 #5 中，注意 $A$ 的每个子串都在 $B$ 中有对应的异序词子串，因此答案为 $10$。

限制条件

$1 \le T \le 100$。

$1 \le L \le 50$。

小数据集（测试集 1 – 可见）

两个字符串 $A$ 和 $B$ 仅由字符 A 和 B 组成。

大数据集（测试集 2 – 隐藏）

无额外限制。

翻译由 DeepSeek V4 Pro 完成