https://leetcode.com/problems/minimum-swaps-to-group-all-1s-together/ (premium)

You’re given a binary array of size n. Find the minimum number of swaps required such that all the 0s and all the 1s are together.

Input Format
The first line of input contains an integer t, denoting the number of test cases. t test case follow. The first line of each test case contains an integer n denoting the size of binary array. The second line contains the binary array.

Output Format
For each test case print the minimum swaps required.

Constraints
1 <= t <= 1000

1 <= n <= 10000

Sample Input
6
4
0011
8
00010111
5
01001
9
011011011
9
010111011
18
100010101011101101
Sample Output
0
1
1
2
1
3

Explanation
For 010111011 one can swap position 2 with 7 resulting in 000111111.