Classic Quotation

Problem Description

When online chatting, we can save what somebody said to form his ''Classic Quotation''. Little Q does this, too. What's more? He even changes the original words. Formally, we can assume what somebody said as a string $S$ whose length is $n$. He will choose a continuous substring of $S$(or choose nothing), and remove it, then merge the remain parts into a complete one without changing order, marked as $S'$. For example, he might remove ''not'' from the string ''I am not SB.'', so that the new string $S'$ will be ''I am SB.'', which makes it funnier. After doing lots of such things, Little Q finds out that string $T$ occurs as a continuous substring of $S'$ very often. Now given strings $S$ and $T$, Little Q has $k$ questions. Each question is, given $L$ and $R$, Little Q will remove a substring so that the remain parts are $S[1..i]$ and $S[j..n]$, what is the expected times that $T$ occurs as a continuous substring of $S'$ if he choose every possible pair of $(i,j)(1\leq i\leq L,R\leq j\leq n)$ equiprobably? Your task is to find the answer $E$, and report $E\times L\times (n-R+1)$ to him. Note : When counting occurrences, $T$ can overlap with each other.

Input

The first line of the input contains an integer $C(1\leq C\leq15)$, denoting the number of test cases. In each test case, there are $3$ integers $n,m,k(1\leq n\leq 50000,1\leq m\leq 100,1\leq k\leq 50000)$ in the first line, denoting the length of $S$, the length of $T$ and the number of questions. In the next line, there is a string $S$ consists of $n$ lower-case English letters. Then in the next line, there is a string $T$ consists of $m$ lower-case English letters. In the following $k$ lines, there are $2$ integers $L,R(1\leq L<R\leq n)$ in each line, denoting a question.

Output

For each question, print a single line containing an integer, denoting the answer.

Sample Input

1

8 5 4

iamnotsb

iamsb

4 7

3 7

3 8

2 7

Sample Output

1

1

0

0

Source

2017 Multi-University Training Contest - Team 4

https://acm.hdu.edu.cn/showproblem.php?pid=6068