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. \)