You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

Time Limit: 2.0 s

Memory Limit: 128.0 MB

Description

You are given a binary string S of length N. In one operation you can do the following:-

• select two distinct indexes i,j. and swap the ith and jth element of string S.
  what is the minimum number of operations you need to sort the string either in non-increasing or non-decreasing order ?

A binary string is a string which contains only '0' and '1'
example of a non increasing string: 11100
example of a non decreasing string: 0000011

Input

fisrst line contains an integer T: number of testcases
first line of each test case contains an integer N: size of the string
second line of each test case contains a string S
1 <= T <= 1000
1 <= N <= \(10^5\)
it is guaranteed that the sum of N over all testcases will not exceed \(10^5\)

Output

output T lines. each line should contian an integer: the minimum number of operations required

Sample

3
2
10
3
010
1
0

0
1
0

in first testcase: the string is already sorted in non increasing order.
in second testcase: we can swap the 2nd and 3rd element to sort the string in non decreasing order