Border Queries

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 $s1$ 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 \leq T \leq 60)$ denoting the number of test cases.

For each test case, the first line contains three integers $n,m,q \: (3 \leq n \leq 10^6, 1 \leq m,q \leq 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 \leq l_i \leq r_i \leq 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.

Example

1
7 7 2
abacaba
cabacab
1 4
3 7

0
2