INS14A - BSTRING

In his next interview Digo is given a binary string of N characters. A binary string is string consisting of only 0's and 1's. Digo can swap any adjacent pair of characters in one operation. Digo has to bring at least M 1's together starting at any position of the string. Help him count the minimum number of operations required to do so.

It is guaranteed that there are at least M 1's present in the given string.

Input

First line contains single integer T. Number of test cases.

Next 2 * T lines represent T test cases. Each test case is described by two lines; first line contains a single integer M and the second line contains the input binary string.

Output

Output T lines, one for each test case containing the answer for that case.

Constraints

1 <= T <= 10
1 <= N <= 50000
1 <= M <= N
Sum of N over all the cases if less than or equal to 50000.

Sample

Input:
2
3
101001
2
101001

Output:
3
1

Added by:Surya Kiran
Date:2014-03-20
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Insomnia 2014

hide comments
2020-12-27 11:10:08
Sliding window, median
2015-01-31 06:41:21 HD :-D
good problem.. ofcourse needs patience
2015-01-25 15:24:38 kelaseek
need a lot of patience
2014-12-30 13:51:12 eightnoteight
are there any tricky testcases, i'm getting wrong answer for 4th testcase
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.