Border Queries

Problem Description

Given a string $S$ of length $n$ consisting of lowercase English letters. A partition of $S$ into three non-empty substrings $s_1,s_2,s_3$ is considered good if and only if $s_1$ is the border of $s_1+s_2$ and $s_3$ is the border of $s_2+s_3$. We say a string $s$ good if and only if $s$ is a substring of $S$ and there exists a good partition of $S$ into $s_1,s_2,s_3$ such that $s_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 $T$ of length $m$ consisting of lowercase English letters and $q$ queries. In each query, you are given two integers $l,r$. You need to calculate the value of $T[l\cdots r]$.

Input

Each test contains multiple test cases. The first line contains an integer $T$ ($1\le T\le 60$) denoting the number of test cases. For each test case, the first line contains three integers $n,m,q$ ($3\le n\le 10^6$, $1\le m,q\le 10^6$). The second line contains a string $S$ of length $n$. The third line contains a string $T$ of length $m$. The next $q$ lines each contains two integers $l_i$ and $r_i$, denoting a query ($1\le l_i\le r_i\le m$). It is guaranteed that $\sum n,\sum m,\sum q$ over all test cases does not exceed $10^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）