题目描述

Margaret researches genetic sequences. She is analysing two sequences $\mathbf{A}$ and $\mathbf{B}$ from a new kind of life that does not use the typical four letter genetic alphabet. The code for the genetic sequences conveniently requires 26 letters represented by the uppercase English letters 'A' through 'Z'.

Margaret wants to compare the sequences $\mathbf{A}$ and $\mathbf{B}$. The best way to do this is to do a series of sequence analysis tests. Each test involves taking a prefix from $\mathbf{A}$ containing only the first $\mathbf{P}$ letters from $\mathbf{A}$, which is called the $\mathbf{A}$-prefix. Each test also involves taking a suffix from $\mathbf{B}$ containing only the last $\mathbf{S}$ letters from $\mathbf{B}$, which is called the $\mathbf{B}$-suffix. Margaret then needs to compare the $\mathbf{A}$-prefix to the $\mathbf{B}$-suffix. A substring is a subsequence of contiguous letters. A substring from the $\mathbf{A}$-prefix matches the $\mathbf{B}$-suffix if the $\mathbf{B}$-suffix starts with that substring. That is, the substring is a prefix of the $\mathbf{B}$-suffix. The result of a test is the length of the longest substring from the $\mathbf{A}$-prefix that matches the $\mathbf{B}$-suffix.

Margaret needs some software to determine the outcome of a batch of $\mathbf{Q}$ sequence analysis tests. Note that each test is independent. Margaret has many copies of $\mathbf{A}$ and $\mathbf{B}$ and a new one is used for each test.

输入格式

The first line of the input gives the number of test cases, $\mathbf{T}$. $\mathbf{T}$ test cases follow. Each test case begins with a line containing two strings and an integer, $\mathbf{A}$, $\mathbf{B}$, and $\mathbf{Q}$ respectively. Each test case ends with $\mathbf{Q}$ lines, the $i$-th of which contains two integers $\mathbf{P}_i$ and $\mathbf{S}_i$, which are the prefix and suffix sizes for the $i$-th sequence analysis test.

输出格式

For each test case, output one line containing Case #$x$: $y_1$ $y_2$ $\ldots$ $y_{\mathbf{Q}}$, where $x$ is the test case number (starting from 1) and $y_i$ is the answer to the $i$-th query in the input.

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

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

提示

Sample Explanation

In Sample Case #1, there are 3 tests. The prefix $\mathbf{A B C}$ from $\mathbf{A}$ and the complete suffix $\mathbf{C A B A B A}$ from $\mathbf{B}$ are compared in the first test. The answer is 1, since $\mathbf{c}$ is the longest substring that is contained in $\mathbf{A B C}$ and is a prefix of $\mathbf{C A B A B A}$. In the second test, $\mathbf{A B C A B A C}$ is tested against $\mathbf{C A B A B A}$ and the longest match is $\mathbf{C A B A}$. In the third test, $\mathbf{A B C A B A}$ is tested against $\mathbf{A B A B A}$ and the longest match is $\mathbf{A B A}$.

In Sample Case #2, there are 2 tests. In the first, $\mathbf{B A N A N}$ is tested against $\mathbf{B A N A}$, and the longest match is $\mathbf{B A N A}$. In the second, $\mathbf{B A N A N}$ is tested against $\mathbf{A B A N A}$, and the longest match is $\mathbf{A}$.

In Sample Case #3, there is one test. In it, $\mathbf{A B}$ is tested against $\mathbf{d}$. Since there is no match the answer is 0.

Limits

• $1 \leq \mathbf{T} \leq 100$.
• $1 \leq \mathbf{P}_{i} \leq$ the length of $\mathbf{A}$.
• $1 \leq \mathbf{S}_{i} \leq$ the length of $\mathbf{B}$.

Test Set 1 (5 Pts, Visible Verdict)

• $1 \leq$ the length of $\mathbf{A} \leq 3000$.
• $1 \leq$ the length of $\mathbf{B} \leq 3000$.
• $1 \leq \mathbf{Q} \leq 3000$.

Test Set 2 (17 Pts, Hidden Verdict)

• $1 \leq$ the length of $\mathbf{A} \leq 10^{5}$.
• $1 \leq$ the length of $\mathbf{B} \leq 10^{5}$.
• The sum of the lengths of $\mathbf{A}$ over all test cases is $\leq 5 \times 10^{5}$
• The sum of the lengths of $\mathbf{B}$ over all test cases is $\leq 5 \times 10^{5}$
• $1 \leq \mathbf{Q} \leq 10^{5}$.