#P7987. Pty loves string

Pty loves string

Pty loves string

Pty has a string SS of length nn consisting of lowercase English letters. He denotes the value of string TT as the number of occurrences of TT in string SS.

Now he has QQ queries, for each query he gives you x,yx,y. Let the string TT be the concatenation of the prefix of length xx in the string SS and its suffix of length yy. He wants you to tell him the value of TT.

The two pieces are concatenated, so ∣T∣=x+y|T|=x+y even when their positions in SS overlap. Count all contiguous occurrences of TT, including overlapping occurrences. If x+y>nx+y>n, the answer is 0.

输入格式

An integer TT in the first line indicates the number of tests.

For each test,first line contains two integer n,Qn,Q - the length of SS and the number of queries.

The second line contains string SS of length nn consisting of lowercase English letters.

For the next QQ lines, each line contains two integers x,yx,y.

$1\le T\le 5,1\le n,Q\le 2\times 10^{5},1\le x,y\le n$

输出格式

For each test,output QQ lines in total.

For each query, print the answer in one line.

样例输入1

1
6 3
ababaa
1 1
2 1
3 1

样例输出1

1
2
1