题目描述

Margaret 正在研究基因序列。她正在分析一种新型生命体的两个序列 $\mathbf{A}$ 和 $\mathbf{B}$，这种生命体不使用典型的四字母遗传密码。基因序列的编码方便地使用了 26 个大写英文字母 'A' 到 'Z' 来表示。

Margaret 想要比较序列 $\mathbf{A}$ 和 $\mathbf{B}$。最佳方法是进行一系列序列分析测试。每个测试需要从 $\mathbf{A}$ 中取出一个前缀（称为 $\mathbf{A}$-前缀），包含 $\mathbf{A}$ 的前 $\mathbf{P}$ 个字母；同时从 $\mathbf{B}$ 中取出一个后缀（称为 $\mathbf{B}$-后缀），包含 $\mathbf{B}$ 的最后 $\mathbf{S}$ 个字母。然后 Margaret 需要比较 $\mathbf{A}$-前缀和 $\mathbf{B}$-后缀。子串是指连续的字母子序列。如果 $\mathbf{B}$-后缀以某个 $\mathbf{A}$-前缀的子串开头，即该子串是 $\mathbf{B}$-后缀的前缀，则称该子串与 $\mathbf{B}$-后缀匹配。测试的结果是 $\mathbf{A}$-前缀中能与 $\mathbf{B}$-后缀匹配的最长子串的长度。

Margaret 需要一些软件来确定一批 $\mathbf{Q}$ 个序列分析测试的结果。注意每个测试都是独立的。Margaret 有 $\mathbf{A}$ 和 $\mathbf{B}$ 的多个副本，每个测试都使用新的副本。

输入格式

输入的第一行给出测试用例的数量 $\mathbf{T}$。随后是 $\mathbf{T}$ 个测试用例。每个测试用例的第一行包含两个字符串和一个整数，分别是 $\mathbf{A}$、$\mathbf{B}$ 和 $\mathbf{Q}$。每个测试用例的最后是 $\mathbf{Q}$ 行，第 $i$ 行包含两个整数 $\mathbf{P}_i$ 和 $\mathbf{S}_i$，表示第 $i$ 个序列分析测试的前缀和后缀大小。

输出格式

对于每个测试用例，输出一行 Case #x: y1 y2 ... yQ，其中 $x$ 是测试用例编号（从 1 开始），$y_i$ 是第 $i$ 个查询的答案。

输入输出样例 #1

输入 #1

3
ABCABAC CABABA 3
3 6
7 6
6 5
BANANA HABANA 2
5 4
5 5
ABC ABD 1
2 1

输出 #1

Case #1: 1 4 3
Case #2: 4 1
Case #3: 0

说明/提示

样例解释

在样例 #1 中，有 3 个测试。第一个测试比较 $\mathbf{A}$ 的前缀 $\mathbf{A B C}$ 和 $\mathbf{B}$ 的完整后缀 $\mathbf{C A B A B A}$。答案是 1，因为 $\mathbf{C}$ 是 $\mathbf{A B C}$ 中包含的最长子串，且是 $\mathbf{C A B A B A}$ 的前缀。第二个测试比较 $\mathbf{A B C A B A C}$ 和 $\mathbf{C A B A B A}$，最长匹配是 $\mathbf{C A B A}$。第三个测试比较 $\mathbf{A B C A B A}$ 和 $\mathbf{A B A B A}$，最长匹配是 $\mathbf{A B A}$。

在样例 #2 中，有 2 个测试。第一个测试比较 $\mathbf{B A N A N}$ 和 $\mathbf{B A N A}$，最长匹配是 $\mathbf{B A N A}$。第二个测试比较 $\mathbf{B A N A N}$ 和 $\mathbf{A B A N A}$，最长匹配是 $\mathbf{A}$。

在样例 #3 中，有一个测试。比较 $\mathbf{A B}$ 和 $\mathbf{D}$。由于没有匹配，答案是 0。

限制

• $1 \leq \mathbf{T} \leq 100$。
• $1 \leq \mathbf{P}_i \leq \mathbf{A}$ 的长度。
• $1 \leq \mathbf{S}_i \leq \mathbf{B}$ 的长度。

测试集 1（5 分，可见评测结果）

• $1 \leq \mathbf{A}$ 的长度 $\leq 3000$。
• $1 \leq \mathbf{B}$ 的长度 $\leq 3000$。
• $1 \leq \mathbf{Q} \leq 3000$。

测试集 2（17 分，隐藏评测结果）

• $1 \leq \mathbf{A}$ 的长度 $\leq 10^5$。
• $1 \leq \mathbf{B}$ 的长度 $\leq 10^5$。
• 所有测试用例中 $\mathbf{A}$ 的长度总和 $\leq 5 \times 10^5$。
• 所有测试用例中 $\mathbf{B}$ 的长度总和 $\leq 5 \times 10^5$。
• $1 \leq \mathbf{Q} \leq 10^5$。