Zero String

You are given a binary string $s$ of length $n$. You are allowed to perform the following types of operations on string $s$:

• Delete any one character from $s$, and concatenate the remaining parts of the string. For example, if we delete the third character of $s=1101$, it becomes $s=111$;

• Flip all the characters of $s$. For example, if we flip all character of $s=1101$, it becomes $s=0010$.

Given that you can use either type of operation any number of times, find the minimum number of operations required to make all characters of the string $s$ equal to $0$.

Input

The first line contains a single integer $t$, denoting the number of test cases. Each test case consists of multiple lines.

The first line of each test case contains an integer $n(1\le n\le 10^5$) — the length of the string. The next line contains a binary string $s$ of length $n$.

It is known that $s$ contains $0$ and $1$ only.

Output

For each test case, output on a new line, the minimum number of operations required to make all characters of the string $s$ equal to $0$.

Examples