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

Margaret 想要比较序列 $\mathbf{A}$ 和 $\mathbf{B}$。最好的方法是进行一系列序列分析测试。每次测试涉及从 $\mathbf{A}$ 中取出一个仅包含前 $P_i$ 个字母的前缀，称为 $\mathbf{A}$-前缀。每次测试还涉及从 $\mathbf{B}$ 中取出一个仅包含最后 $S_i$ 个字母的后缀，称为 $\mathbf{B}$-后缀。然后，Margaret 需要将该 $\mathbf{A}$-前缀与该 $\mathbf{B}$-后缀进行比较。子串是连续字母的子序列。如果 $\mathbf{A}$-前缀中的某个子串与 $\mathbf{B}$-后缀匹配，则意味着该 $\mathbf{B}$-后缀以该子串开头。也就是说，该子串是 $\mathbf{B}$-后缀的一个前缀。测试的结果是 $\mathbf{A}$-前缀中与 $\mathbf{B}$-后缀匹配的最长子串的长度。

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

输入格式

输入的第一行给出了测试用例的数量 $T$。接下来是 $T$ 个测试用例。每个测试用例的第一行包含两个字符串和一个整数，分别是 $\mathbf{A}$、$\mathbf{B}$ 和 $Q$。每个测试用例以 $Q$ 行结束，第 $i$ 行包含两个整数 $P_i$ 和 $S_i$，分别是第 $i$ 次序列分析测试的 $\mathbf{A}$-前缀长度和 $\mathbf{B}$-后缀长度。

输出格式

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

数据范围

$1 \le T \le 100$ $1 \le P_i \le \text{length of } \mathbf{A}$ $1 \le S_i \le \text{length of } \mathbf{B}$

测试集 1（可见判定）

$1 \le \text{length of } \mathbf{A} \le 3000$ $1 \le \text{length of } \mathbf{B} \le 3000$ $1 \le Q \le 3000$

测试集 2（隐藏判定）

$1 \le \text{length of } \mathbf{A} \le 10^5$ $1 \le \text{length of } \mathbf{B} \le 10^5$ 所有测试用例中 $\mathbf{A}$ 的长度之和 $\le 5 \times 10^5$ 所有测试用例中 $\mathbf{B}$ 的长度之和 $\le 5 \times 10^5$ $1 \le Q \le 10^5$

样例

样例输入 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}$ 的前缀 ABC 和来自 $\mathbf{B}$ 的完整后缀 CABABA。答案是 1，因为 C 是包含在 ABC 中且是 CABABA 前缀的最长子串。在第二次测试中，ABCABAC 与 CABABA 进行测试，最长匹配是 CABA。在第三次测试中，ABCABA 与 ABABA 进行测试，最长匹配是 ABA。

在样例 2 中，有 2 次测试。在第一次测试中，BANAN 与 BANA 进行测试，最长匹配是 BANA。在第二次测试中，BANAN 与 ABANA 进行测试，最长匹配是 A。

在样例 3 中，只有一次测试。其中，AB 与 D 进行测试。由于没有匹配，答案为 0。