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

\(1 \leq T \leq 10^5 \\ 1 \leq N \leq 3\cdot10^5\\ \\S \; contains\; '0's\; and\; '1's. \\ Sum\; of \; N\;over\;all\;test\;cases\;does\;not\;exceed\;3\cdot 10^5. \)