Zero String#11426
You are given a binary string of length . You are allowed to perform the following types of operations on string :
Delete any one character from , 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 . 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 equal to .
The first line contains a single integer , denoting the number of test cases. Each test case consists of multiple lines.
The first line of each test case contains an integer (1 \le n \le 10^5) — the length of the string. The next line contains a binary string of length .
It is known that contains and only.
For each test case, output on a new line, the minimum number of operations required to make all characters of the string equal to .
Example 1