#P9908. Border Queries

    ID: 8130 传统题 2000ms 512MiB 尝试: 2 已通过: 2 难度: 8 上传者: 标签>CF2400字符串KMP后缀自动机前缀和2023“钉耙编程”中国大学生算法设计超级联赛(10)

Border Queries

Border Queries

Problem Description

Given a string SS of length nn consisting of lowercase English letters. A partition of SS into three non-empty substrings s1,s2,s3s_1,s_2,s_3 is considered good if and only if s1s_1 is the border of s1+s2s_1+s_2 and s3s_3 is the border of s2+s3s_2+s_3. We say a string ss good if and only if ss is a substring of SS and there exists a good partition of SS into s1,s2,s3s_1,s_2,s_3 such that s2=ss_2=s. Define the value of a string as the number of its good substrings. Two substrings are considered different if and only if the start position is different or the end position is different. Given a string TT of length mm consisting of lowercase English letters and qq queries. In each query, you are given two integers l,rl,r. You need to calculate the value of T[l⋯r]T[l\cdots r].

Input

Each test contains multiple test cases. The first line contains an integer TT (1≤T≤601\le T\le 60) denoting the number of test cases. For each test case, the first line contains three integers n,m,qn,m,q (3≤n≤1063\le n\le 10^6, 1≤m,q≤1061\le m,q\le 10^6). The second line contains a string SS of length nn. The third line contains a string TT of length mm. The next qq lines each contains two integers lil_i and rir_i, denoting a query (1≤li≤ri≤m1\le l_i\le r_i\le m). It is guaranteed that ∑n,∑m,∑q\sum n,\sum m,\sum q over all test cases does not exceed 10610^6.

Output

For each query, output one line with an integer denoting the answer. Please do not output trailing spaces.

Sample Input

1
7 7 2
abacaba
cabacab
1 4
3 7

Sample Output

0
2

Source

2023“钉耙编程”中国大学生算法设计超级联赛(10)