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.
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≤n≤105) — 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.
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.