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.