CRAN04 - Audition

Penny is a terrible waitress and even worse actress, however recently she applied for a role in an upcoming TV series. Even though she thought she had no chance, she was called for an audition. She was very happy about it until she found out that her character in this new series will be a studious, high IQ girl named Megan. Producer told her that to get the role of Megan she had to prove that her mind can handle a bit of mathematics and reasoning. If she passed the test then she will be given the role of Megan. The test was as follow.

The people (Boys and Girls) who came for audition are standing in a line in a random order. Producer has to select exactly K boys for the show. So he asks Penny to tell how many ways can he select two numbers i and j such that the number of boys standing between these (including I and j) indexes is exactly K.

Penny desperately needs this role. Everybody knows that Penny is not a very smart and requests you to help her.

Input

First line contains T – The number of test cases.

Next line contains space separated N and K.

N – The total number of boys and girls who came to audition.

K – The number of the boys who must be there between each (i, j) pair.

Next line contains a non-empty string consisting of '1' and '0'.

1 represents Boy.

0 represents Girl.

Output

The number of (i, j) pairs such that the number of boys between index i and j, both inclusive is equal to K.

Constraints

1<=T<=10

1<=N<=10^6

0<=K<=10^6

Example

Input:
3
4 1
0101
5 2
01010
5 4
01010

Output:
6
4
0

Added by:CSI
Date:2013-02-16
Time limit:2s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64

hide comments
2021-03-20 08:43:12
using ds which have logn tc may lead to tle.
use ds with o(1) tc
2020-09-14 00:58:51
Be careful of K=0. Depending on your solution, it will make you get wrong answer after 7th case
2020-08-03 13:12:38
take care of overflows :p
2019-11-11 16:26:22
two pointer got AC
keep cosidaration when k=0 ..
happy coding
2019-07-18 18:57:49
take care of the case with k=0 , and ans can be very large , nd there is a O(n) solution and i=j is a valid pair too


Last edit: 2019-07-18 18:59:33
2018-08-12 00:25:47
AC O(n) solution with 2 pointers
2018-03-17 20:57:40
Using Dp but gettin WA in 7th test case ...
Can someone help with the corner cases?
2017-11-13 06:39:27 Hugo Godoy
May I assume that the string has length N?
2017-09-02 09:47:16
did using binary search O(nlogn) solution.
Don't know how to solve in O(n).
Any Hint ??
2017-06-27 08:55:00 hacker_sk
3rd rank with O(n) soln. :)
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.