问题 J: Border Queries

Given a string $S$ of length $n$ consisting of lowercase English letters. A partition of $S$ into three non-empty substrings �1,�2,�3s1,s2,s3 is considered good if and only if �1s1 is the border of �1+�2s1+s2 and �3s3 is the border of �2+�3s2+s3. 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 �1,�2,�3s1,s2,s3 such that �2=�s2=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]$.

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≤�≤1063≤n≤106, 1≤�,�≤1061≤m,q≤106).

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 ��li and ��ri, denoting a query (1≤��≤��≤�1≤li≤ri≤m).

It is guaranteed that $\sum n,\sum m,\sum q$ over all test cases does not exceed 106106.

For each query, output one line with an integer denoting the answer.

Please do not output trailing spaces.