CF2266C.AND, OR, Sort!

You are given a binary string$^{\text{∗}}$ $s$ of length $n$.

You may perform the following operation any number of times (possibly zero):

• choose an integer $i$ ($1 \le i \le n$), and replace $s_i$ with either the bitwise AND or the bitwise OR of $s_1, s_2, \ldots, s_i$.

Note that the bitwise AND or bitwise OR of a single element is equal to the element itself.

Your goal is to make $s$ sorted in non-decreasing order$^{\text{†}}$.

Find the minimum number of operations required to sort $s$ in non-decreasing order.

$^{\text{∗}}$A binary string only contains characters $\texttt{0}$ and $\texttt{1}$.

$^{\text{†}}$If $s$ is in non-decreasing order, then $s_1 \leq s_2 \leq \ldots \leq s_n$.

给你一个长度为 $n$ 的二进制字符串$^{\text{∗}}$ $s$。

你可以执行以下操作任意次（可以为零次）：

• 选择一个整数 $i$（$1 \le i \le n$），并将 $s_i$ 替换为 $s_1, s_2, \ldots, s_i$ 的按位与或按位或结果。

注意：单个元素的按位与或按位或结果即为该元素本身。

你的目标是使 $s$ 按非递减顺序$^{\text{†}}$ 排列。

求使 $s$ 变为非递减顺序所需的最少操作次数。

$^{\text{∗}}$二进制字符串仅包含字符 $\texttt{0}$ 和 $\texttt{1}$。

$^{\text{†}}$若 $s$ 是非递减顺序的，则满足 $s_1 \leq s_2 \leq \ldots \leq s_n$。

The first line contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases.

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

The second line of each test case contains the binary string $s$ of length $n$. Each character of $s$ is either 0 or 1.

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

第一行包含一个整数 $t$（$1 \le t \le 10^4$）—— 测试用例的数量。

每个测试用例的第一行包含一个整数 $n$（$2 \le n \le 2 \cdot 10^5$）—— 二进制字符串 $s$ 的长度。

每个测试用例的第二行包含长度为 $n$ 的二进制字符串 $s$，其中 $s$ 的每个字符均为 0 或 1。

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

For each test case, print a single integer — the minimum number of operations required to sort $s$ in non-decreasing order.

对于每个测试用例，输出一个整数——将 $s$ 按非递减顺序排序所需的最少操作次数。

In the first test case, the string is already sorted, so no operations are required.

In the second test case, we can use bitwise OR to change the last three characters to 1, obtaining 1111 in $3$ operations.

在第一个测试用例中，字符串已经排好序，因此不需要执行任何操作。

在第二个测试用例中，我们可以使用按位或（bitwise OR）操作将最后三个字符变为 1，从而在 $3$ 次操作内得到 1111。