Shoumik loves problem solving but he is weak in string related problems. 

So he is practicing string  related problems. But he thought that creating 

a string related problem and solving that would be a great idea to be 

strong in strings. So he thought of a problem.

 

Given a string S of N lower case alphabets how many distinct substrings T 

are there with length L( L=|T| ) and S contains exactly X occurrences of T. 

In the string S=“abcbcb” the substring T=“bcb” has length L=3 and S 

has X=2 occurrences of T.(See hints for more clarification)

 

But as Shoumik is weak in string, he is stuck with this problem. You have 

to help him answering Q queries for a given string S.

Input

First line of input will contain the number of test cases Ts.

Then Ts test cases follows. Every test case contains two integers

N and Q in the first line. Next line will contain a string S, consisting of

N lower casecharacters. The next Q lines will contain Q queries with

two integers L,length of T for this query and X, Occurrences of T in S.

 

1<=Ts<=15

1<=N<=10000

1<=Q<=100000

1<=L<2^31

0<=X<2^31

Sum of N over all test cases <=60000 (6*10^4)
Number of queries Q over all test cases <= 600000 (6*10^5)

Output

For every query print the number of distinct substrings T in the string S 

which are of length L and have exactly X occurrences in S.

Example

Input:

1

6 5

abcbcb

3 2

4 1

6 2

6 1

1 2

Output:
1

3

0

1

1
 

Hints

For the 2nd query we have 3 distinct substrings of length 4 “abcb”,“bcbc”,

“cbcb” and all of them have 1 occurrence in S. So the answer is 3.

 

For the 5th query we have 3 distinct substrings of length 1 “a”,“b”,“c”

but only “c” has 2 occurrences in S. So the answer is 1.