A suffix array for string of length is a permutation of integers from to such that is the list of non-empty suffixes of sorted in lexicographical order. The rank table for suffixex of is a permutation of integers from to such that .

Kotori has a string . She would like to ask queries. And in the -th query, a substring of is given, Kotori would like to know the rank of suffix of .

Note means the substring of which starts from the -th position and ends at the -th position, both inclusive.

输入描述:

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

The first line contains two integers  and  () -- the length of the string and the number of queries.

The second line contains a string  of length  consisting only of lowercase English letters.

Each of the next  lines contains three integers ,  and  () denoting a query.

It is guaranteed that neither the sum of  or the sum of  of all test cases will exceed .

输出描述:

For each query output one line containing one integer denoting the answer.

2
10 4
baaabbabba
2 8 3
1 1 1
2 3 2
2 5 4
20 3
cccbccbadaacbbbcccab
14 17 16
3 20 17
17 20 18

2
1
2
3
4
15
3