Problem Description

Pty has a string S of length n consisting of lowercase English letters. He denotes the value of string T as the number of occurrences of T in string S.

Now he has Q queries, for each query he gives you x,y. Let the string T be the concatenation of the prefix of length x in the string S and its suffix of length y. He wants you to tell him the value of T.

Input

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

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

The second line contains string S of length n consisting of lowercase English letters.

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

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

Output

For each test,output Q lines in total.

For each query, print the answer in one line.

1
6 3
ababaa
1 1
2 1
3 1

1
2
1