You are given a string S of length N consisting only of 0s and 1s. You are also given an integer K.
You have to answer Q queries. In the i^th query, two integers Li and Ri are given. Then you should print the number of substrings of S[L, R] which contain at most K 0s and at most K 1s where S[L, R] denotes the substring from L^th to R^th characters of the string S.
In other words, you have to count number of pairs (i, j) of integers such that L ≤ i ≤ j ≤ R such that no character in substring S[i, j] occurs more than K times.

Input
The first line of input contains an integer T, denoting the number of test cases. Then T test cases follow.
The first line of each test case contains three space-separated integers N, K and Q as described in the problem. The second line contains a string S of length N. Then the next Q lines describe the query, where the i^th line of them contains two space-separated integers Li and Ri.

Output
For each query, print the required answer in a single line.

Constraints and Example
Input:
1
8 2 3
01110000
1 4
2 4
5 8

Output:
8
5
7

Explanation
Query 1: Consider substring P = S[1, 4] = "0111".Out of 10 total substrings of P, substrings P[1, 4] and P[2, 4] are not valid because both contain more than two 1s. Other substrings contains at most two 0s and at most two 1s, thus the answer is 8.
Query 2: Consider substring P = S[2, 4] = "111".Out of 6 total substrings of P, substrings P[1, 3] is not valid because it contains more than two 1s.
Query 3: Consider substring P = S[5, 8] = "0000".Out of 10 total substrings of P, substrings P[1, 3], P[1, 4] and P[2, 4] are not valid because all contain more than two 0s.

见题面

见题面