You are given a binary string \(S\) of length \(N\). You can apply the following operation to the string \(S\) :

• Choose two distinct indices \(i, j\;(1 \le i, j\le N, i\neq j)\) and flip the characters \(S_i, S_j\).

Find the minimum number of operations required to sort the given string \(S\). It is always possible to sort any string under the given constraints.

Input format

• The first line contains \(T\) denoting the number of test cases. The description of \(T\) test cases is as follows:
• For each test case:
  • The first line contains \(N\) denoting the length of string \(S\).
  • The second line contains the binary string \(S\).

Output format

For each test case, print the minimum number of operations required to sort the given string \(S\).

Constraints