二进制字符串是仅由字符 0 和 1 组成的字符串。您将获得一个二进制字符串 $$$s_1 s_2 \ldots s_n$$$。需要用最少的操作次数使这个字符串不减。换句话说,每个字符不应小于前一个字符。在一项操作中,您可以执行以下操作:
- 选择字符串中的任意索引 $$$1 \leq i \leq n$$$;
- 对于所有$$$j \geq i$$$,将第$$$j$$$位置的值改为相反,即如果$$$s_j = 1$$$,则使$$$s_j = 0$$$,反之亦然。
使字符串不减最少需要多少次操作?
输入
每个测试由多个测试用例组成。第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — 测试用例的数量。测试用例的描述如下。
每个测试用例的第一行是一个整数 $$$n$$$ ($$$1 \leq n \leq 10^5$$$) — 字符串的长度。
每个测试用例的第二行包含一个长度为$$$n$$$的二进制字符串$$$s$$$。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。
输出
对于每个测试用例,输出一个整数 - 使字符串不递减所需的最少操作数。
示例
输入 #1
8 1 1 2 10 3 101 4 1100 5 11001 6 100010 10 0000110000 7 0101010
输出 #1
0 1 2 1 2 3 1 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}$$$。