Welcome to ZOJ
 Problem Sets Information Select Problem Runs Ranklist
ZOJ Problem Set - 4030
JUMPin' JUMP UP!!!

Time Limit: 1 Second      Memory Limit: 131072 KB

Tired of solving mathematical equations, DreamGrid starts to solve equations related to strings: for two strings $x$ and $y$ with the same length consisting of lowercase English letters, calculate $f(x,y,n)$, which is defined as the number of nonempty strings $z$ consisting of lowercase English letters such that $xz=zy$ and the length of $z$ does not exceed $n$.

DreamGrid has two strings $s=s_{1}s_{2}\dots s_{n}$ and $t=t_{1}t_{2}\dots t_{m}$. He would like to ask several questions about the value of $f(t, s[x..(x+m-1)], y)$, where $s[x..(x+m-1)]$ is the substring of $s$ starting from $s_x$ with length $m$ and $y$ is a given number.

Input

There are multiple test cases. The first line of input contains an integer $T$, indicating the number of test cases. For each test case:

The first line contains three integers $n$ and $m$ and $q$ ($1 \le n, m, q \le 10^5, m \le n$) -- the length of $s$, the length of $t$ and the number of questions.

The second line contains $n$ lowercase English letters denoting the string $s$. The third line contains $m$ lowercase English letters denoting the string $t$.

Each of the next $q$ lines contains two integers $x_i$ and $y_i$ ($1 \le x_i \le n + 1 - m, 1 \le y_i \le 10^{18}$) denoting the $i$-th question.

It is guaranteed that neither the sum of all $n$ nor the sum of all $q$ exceeds $10^6$.

Output

For each question, output an integer denoting the answer.

Sample Input

1
4 2 3
abcd
ba
1 2
2 2
3 2


Sample Output

1
0
0


Author: LIN, Xi
Source: The 15th Zhejiang Provincial Collegiate Programming Contest Sponsored by TuSimple
Submit    Status