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³¹

0 ≤ X < 2³¹

Sum of N over all test cases ≤ 60000 (6×10⁴)

Number of queries Q over all test cases ≤ 600000 (6×10⁵)

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.