#P7987. Pty loves string
Pty loves string
Pty loves string
Pty has a string of length consisting of lowercase English letters. He denotes the value of string as the number of occurrences of in string .
Now he has queries, for each query he gives you . Let the string be the concatenation of the prefix of length in the string and its suffix of length . He wants you to tell him the value of .
The two pieces are concatenated, so even when their positions in overlap. Count all contiguous occurrences of , including overlapping occurrences. If , the answer is 0.
输入格式
An integer in the first line indicates the number of tests.
For each test,first line contains two integer - the length of and the number of queries.
The second line contains string of length consisting of lowercase English letters.
For the next lines, each line contains two integers .
$1\le T\le 5,1\le n,Q\le 2\times 10^{5},1\le x,y\le n$
输出格式
For each test,output 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