H. Substring Symphony
time limit per test
4 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

You are given two strings $$$a$$$ and $$$b$$$, where $$$a$$$ has length $$$n$$$ and $$$b$$$ has length $$$m$$$.

For a string $$$c$$$, define $$$f(c)$$$ as the number of distinct integers $$$k$$$ ($$$1 \leq k \leq |c|$$$) such that every $$$k$$$-length contiguous substring of $$$c$$$ is also a contiguous substring of $$$a$$$.

Your task is to answer $$$q$$$ queries. In each query, you are given two integers $$$l$$$ and $$$r$$$, and you need to compute $$$f(b[l:r])$$$, where $$$b[l:r]$$$ denotes the contiguous substring of $$$b$$$ starting at index $$$l$$$ and ending at index $$$r$$$.

Input

The first line contains a single integer $$$t$$$ ($$$1 \leq t \leq 10^5$$$) — the number of test cases.

The first line of each test case contains three integers $$$n$$$, $$$m$$$, and $$$q$$$ ($$$1 \leq n, m \leq 4 \cdot 10^5$$$, $$$1 \leq q \leq 10^6$$$) — the lengths of strings $$$a$$$ and $$$b$$$, and the number of queries.

The second line contains the string $$$a$$$ of length $$$n$$$ consisting of lowercase English letters.

The third line contains the string $$$b$$$ of length $$$m$$$ consisting of lowercase English letters.

Each of the next $$$q$$$ lines contains two integers $$$l$$$ and $$$r$$$ ($$$1 \leq l \leq r \leq m$$$).

It is guaranteed that the sum of $$$n$$$ and the sum of $$$m$$$ over all test cases does not exceed $$$4 \cdot 10^5$$$, and the sum of $$$q$$$ over all test cases does not exceed $$$10^6$$$.

Output

For each query, output a single integer — the value of $$$f(b[l:r])$$$.

Example
Input
2
5 5 3
abdbc
cabce
2 4
5 5
3 4
2 3 1
aa
abc
1 1
Output
2
0
2
1
Note

In the first test case, for the first query, we have $$$a = $$$ abdbc and $$$c = b[2:4] = $$$ abc. Here,

  • For $$$k = 1$$$, the $$$1$$$-length substrings of $$$c$$$ are a, b, c. All of these appear in $$$a$$$, so $$$k = 1$$$ is valid.
  • For $$$k = 2$$$, the $$$2$$$-length substrings of $$$c$$$ are ab, bc. Both appear in $$$a$$$, so $$$k = 2$$$ is valid.
  • For $$$k = 3$$$, the $$$3$$$-length substring of $$$c$$$ is abc. This does not appear in $$$a$$$, so $$$k = 3$$$ is not valid.
Therefore, $$$f(c) = 2$$$ as for two different values of $$$k$$$, the substrings of $$$c$$$ appear in $$$a$$$.