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.
def sumv(fr, to):
    num = to - fr + 1
    return (to + fr) * num / 2
t = int(raw_input())
for i in xrange(t):
    n, k, q = map(int, raw_input().split())
    s = raw_input().rstrip()
    cnt = 0
    c1 = 0
    c0 = 0
    far = [0 for x in xrange(n)]
    for j in xrange(n):
        while (c0 == k and s[j] == '0') or (c1 == k and s[j] == '1'):
            far[cnt] = j - 1
            if s[cnt] == '0':
                c0 -= 1
            else:
                c1 -= 1
            cnt += 1
        if s[j] == '0':
            c0 += 1
        else:
            c1 += 1
    for j in xrange(cnt, n):
        far[j] = n - 1
    cdf = [0 for x in xrange(n)]
    cdf[0] = far[0]
    for j in xrange(1, n):
        cdf[j] = cdf[j - 1] + far[j]
    last = [None for x in xrange(n)]
    pre = None
    r = n - 1
    for j in xrange(n - 1, -1, -1):
        if pre == None or pre != far[j]:
            pre = far[j]
            ind = j
        while r >= pre:
            last[r] = ind
            r -= 1
    for j in xrange(q):
        l, r = map(int, raw_input().split())
        l -= 1
        r -= 1
        res = 0
        h = last[r]
        if l <= h:
            if l == 0:
                res += cdf[h]
            else:
                res += cdf[h] - cdf[l - 1]
            res += r * (r - h)
            res -= sumv(l - 1, r - 1)
        else:
            res += sumv(1, r - l + 1)
        print res