유전자 서열

제한

시간 제한: 20초. 메모리 제한: 2 GB. $1 \le \mathbf{T} \le 100$. $\mathbf{A}$의 길이는 $1 \leq \mathbf{P_i} \leq$. $\mathbf{B}$의 길이는 $1 \leq \mathbf{S_i} \leq$.

테스트 세트 1 (결과 공개)

$\mathbf{A} \le 3000$의 길이는 $1 \le$. $\mathbf{B} \le 3000$의 길이는 $1 \le$. $1 \le \mathbf{Q} \le 3000$.

테스트 세트 2 (결과 비공개)

$\mathbf{A} \le 10^5$의 길이는 $1 \le$. $\mathbf{B} \le 10^5$의 길이는 $1 \le$. 모든 테스트 케이스에 대한 $\mathbf{A}$의 길이의 합은 $\leq 5 \times 10^5$이다. 모든 테스트 케이스에 대한 $\mathbf{B}$의 길이의 합은 $\leq 5 \times 10^5$이다. $1 \le \mathbf{Q} \le 10^5$.

입력의 첫 번째 줄에는 테스트 케이스의 수 $\mathbf{T}$가 주어진다. 이어서 $\mathbf{T}$개의 테스트 케이스가 주어진다. 각 테스트 케이스는 각각 두 문자열과 하나의 정수인 $\mathbf{A}$, $\mathbf{B}$, $\mathbf{Q}$이 포함된 줄로 시작한다. 각 테스트 케이스의 마지막에는 $\mathbf{Q}$개의 줄이 주어지며, 그중 $i$-번째 줄에는 $i$-번째 서열 분석 테스트의 접두사와 접미사 크기를 나타내는 두 정수 $\mathbf{P_i}$과 $\mathbf{S_i}$가 주어진다.

각 테스트 케이스에 대해 Case #$x$: $y_1 ~ y_2 ~ \dots ~ y_{\mathbf{Q}}$을 포함하는 한 줄을 출력한다. 여기서 $x$는 (1부터 시작하는) 테스트 케이스 번호이고, $y_i$은 입력의 $i$-번째 질의에 대한 답이다.

예제 케이스 #1에는 3개의 테스트가 있다. 첫 번째 테스트에서는 $\mathbf{A}$의 접두사 ABC과 $\mathbf{B}$의 전체 접미사 CABABA을 비교한다. ABC에 포함되면서 CABABA의 접두사인 가장 긴 부분 문자열이 C이므로 답은 1이다. 두 번째 테스트에서는 ABCABAC을 CABABA과 대조하며, 가장 긴 일치 문자열은 CABA이다. 세 번째 테스트에서는 ABCABA을 ABABA과 대조하며, 가장 긴 일치 문자열은 ABA이다.

예제 케이스 #2에는 2개의 테스트가 있다. 첫 번째 테스트에서는 BANAN을 BANA과 대조하며, 가장 긴 일치 문자열은 BANA이다. 두 번째 테스트에서는 BANAN을 ABANA과 대조하며, 가장 긴 일치 문자열은 A이다.

예제 케이스 #3에는 테스트가 하나 있다. 이 테스트에서는 AB을 D과 대조한다. 일치하는 문자열이 없으므로 답은 0이다.