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 atleast 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 gauranteed that there are atleast M 1's present in the given string.

Input Format:

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 Format:

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

Sample Output:

3
1