题目描述

一个二进制字符串是只包含字符 $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$。

请问，最少需要多少次操作才能使字符串变为非递减的？

输入格式

每个测试点包含多组测试数据。第一行包含一个整数 $t$（$1 \leq t \leq 10^4$），表示测试数据组数。接下来是每组测试数据的描述。

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

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

保证所有测试数据中 $n$ 的总和不超过 $2 \times 10^5$。

输出格式

对于每组测试数据，输出一个整数，表示将字符串变为非递减所需的最少操作次数。

说明/提示

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

在第二个测试用例中，可以选择 $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}$。

由 ChatGPT 4.1 翻译

样例

8
1
1
2
10
3
101
4
1100
5
11001
6
100010
10
0000110000
7
0101010

0
1
2
1
2
3
1
5