CF1732B.Ugu

A binary string is a string consisting only of the characters 0 and 1. You are given a binary string $s_1 s_2 \ldots s_n$. It is necessary to make this string non-decreasing in the least number of operations. In other words, each character should be not less than the previous. In one operation, you can do the following:

• Select an arbitrary index $1 \leq i \leq n$ in the string;
• For all $j \geq i$, change the value in the $j$-th position to the opposite, that is, if $s_j = 1$, then make $s_j = 0$, and vice versa.

What is the minimum number of operations needed to make the string non-decreasing?

二进制字符串是指仅由字符 0 和 1 组成的字符串。给定一个二进制字符串 $s_1 s_2 \ldots s_n$。你需要用最少的操作次数，使该字符串变为非递减的，即每个字符都不小于其前一个字符。每次操作可执行以下步骤：

• 在字符串中任选一个下标 $1 \leq i \leq n$；
• 对所有 $j \geq i$，将第 $j$ 位的值取反：若 $s_j = 1$，则变为 $0$；若 $s_j = 0$，则变为 $1$。

问：使该字符串变为非递减所需的最少操作次数是多少？

Each test consists of multiple test cases. The first line contains an integer $t$ ($1 \leq t \leq 10^4$) — the number of test cases. The description of test cases follows.

The first line of each test cases a single integer $n$ ($1 \leq n \leq 10^5$) — the length of the string.

The second line of each test case contains a binary string $s$ of length $n$.

It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$.

每个测试包含多个测试用例。第一行包含一个整数 $t$（$1 \leq t \leq 10^4$），表示测试用例的数量。随后是各测试用例的描述。

每个测试用例的第一行包含一个整数 $n$（$1 \leq n \leq 10^5$），表示字符串的长度。

每个测试用例的第二行包含一个长度为 $n$ 的二进制字符串 $s$。

保证所有测试用例的 $n$ 之和不超过 $2 \cdot 10^5$。

For each test case, output a single integer — the minimum number of operations that are needed to make the string non-decreasing.

对于每个测试用例，输出一个整数——使字符串变为非递减所需的最少操作次数。

In the first test case, the string is already non-decreasing.

In the second test case, you can select $i = 1$ and then $s = \mathtt{01}$.

In the third test case, you can select $i = 1$ and get $s = \mathtt{010}$, and then select $i = 2$. As a result, we get $s = \mathtt{001}$, that is, a non-decreasing string.

In the sixth test case, you can select $i = 5$ at the first iteration and get $s = \mathtt{100001}$. Then choose $i = 2$, then $s = \mathtt{111110}$. Then we select $i = 1$, getting the non-decreasing string $s = \mathtt{000001}$.

在第一个测试用例中，字符串本身已经是非递减的。

在第二个测试用例中，你可以选择 $i = 1$，从而得到 $s = \mathtt{01}$。

在第三个测试用例中，你可以先选择 $i = 1$，得到 $s = \mathtt{010}$；然后选择 $i = 2$，最终得到 $s = \mathtt{001}$，即一个非递减字符串。

在第六个测试用例中，你可以在第一次操作时选择 $i = 5$，得到 $s = \mathtt{100001}$；接着选择 $i = 2$，得到 $s = \mathtt{111110}$；最后选择 $i = 1$，得到非递减字符串 $s = \mathtt{000001}$。