WEAKSMK - Shoumiks Weakness

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 letters 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 T. Then T 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 lowercase characters.

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 <= T <= 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.


Added by:sahedsohel
Date:2016-09-09
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 GOSU
Resource:https://algo.codemarshal.org/contests/goc-0101

hide comments
2017-03-18 18:44:05
Can someone please give some hint


Last edit: 2017-03-18 18:44:36
2016-09-13 22:58:43 sahedsohel
thanks @prabhakar_jha examples are correct now..!!

Last edit: 2016-09-13 22:59:11
2016-09-13 20:53:51
@sahedsohel:
In the description of the problem you have mentioned as "First line of input will contain the number of test cases Ts"
but in the example of input it doesn't contains the Test case as input
please clear in input there is test case or not.
thnx
2016-09-13 07:50:25 sahedsohel
@abhishekpal : we cannot have any substring of bigger size then the given string..!! given that the constraints are OK...!! I suggest u read the prob again..!!
2016-09-09 20:49:24
@sahedsohel :with a string of length 1000000 how can we have have a substring of size 2^31 and the input you provided doesn't consists of the tasks
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.