题目描述
Ma5termind is very fond of ice-creams. He bought himself N ice-creams of two types which are represented in the form of string of 0's and 1's such that 0 represents ice-cream of type 1 and 1 represents ice-cream of other type. Now he is in dilemma to eat which ice-cream first.So to make things simple he decided to eat all ice-cream of one type first and then the other type ice-cream. But ice-cream of both types are arranged in random order. He can perform a swap operation in which he can swap ice-cream from any position i and j.
Now ma5termind wants to seggregate ice-cream of two types in minimum possible number of swaps otherwise ice cream will melt and he will become sad.
Help him figure out the minimum number of swaps needed.
Input:
Each input file will contain a T test case.
First line will contain N the number of ice-creams and the next line will contain a string of 0's and 1's denoting the types of ice-creams.
Ouput:
For each testcase print a single integer denoting the minimum swaps.
Constraints:
1 ≤ T ≤ 5
1 ≤ N ≤ 10^5
See sample I/O for more clarification.
Scoring:
subtask 1: 1 ≤ N ≤ 1000 ( 20 pts )
subtask 2: 1 ≤ N ≤ 10^5 ( 80 pts )
SAMPLE INPUT
2
4
1001
4
1010
SAMPLE OUTPUT
1
1
Explanation
In the first sample test we can get 1100 by swaping ice-cream from position 2nd and 4th and swaps operations performed will be 1.
输入格式
见题面
输出格式
见题面