给你一个长度为 $$$n$$$ 的二进制字符串 $$$s$$$ 和一个带有两个按钮的打字机: 0 和 1。最初,您的手指位于按钮上 0。您可以进行以下两种操作:
- 按下手指当前所在的按钮。这将打印出按钮上的字符。
- 将手指移至另一个按钮。如果您的手指放在按钮上 0,将其移至按钮 1,反之亦然。
的 成本 二进制字符串的 被定义为键入整个字符串所需的最少操作数。
在输入之前,您最多可以反转$$$s$$$中的一个子串$$$^{\text{*}}$$$。更正式地说,您可以选择两个索引 $$$1\le l\le r\le n$$$,然后反转子字符串 $$$s_{l\ldots r}$$$,从而生成新字符串 $$$s_1s_2\ldots s_{l-1}s_rs_{r-1}\ldots s_ls_{r+1}\ldots s_n$$$。
你的任务是找到通过对 $$$s$$$ 执行最多一次子字符串反转而获得的所有字符串中的最小可能成本。
$$$^{\text{*}}$$$ 字符串 $$$a$$$ 是字符串 $$$b$$$ 的子字符串,如果 $$$a$$$ 可以通过从 $$$b$$$ 删除开头的几个(可能是零个或全部)字符和从末尾删除几个(可能是零个或全部)字符来获得。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1\le n\le 2\cdot 10^5$$$) — 二进制字符串 $$$s$$$ 的长度。
每个测试用例的第二行包含一个二进制字符串 $$$s_1s_2\ldots s_n$$$ ($$$s_i = \mathtt{0}$$$ 或 $$$s_i = \mathtt{1}$$$) - 二进制字符串 $$$s$$$ 的字符。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。
输出
对于每个测试用例,输出最多执行一次子串反转后字符串 $$$s$$$ 的最小成本。
示例
输入复制
63000311130113100510101191101010010011011100
输出复制
3 4 4 4 8 29
注意
在第一个测试用例中,我们可以选择不反转任何子字符串。我们可以执行 3 次 $$$1$$$ 操作来输入 000.
在第二个测试用例中,我们可以选择不反转任何子字符串。我们可以执行 $$$2$$$ 操作将手指移动到按钮 1。然后,我们执行$$$1$$$操作3次来输入 111.
在第三个测试用例中,我们可以选择不反转任何子字符串。我们可以执行$$$1$$$操作来输入 0。然后,我们执行操作 $$$2$$$ 将手指移动到按钮 1。最后,我们执行两次 $$$1$$$ 操作来输入 11,得到最终的字符串 011 仅使用 $$$4$$$ 操作。
在第四个测试用例中,我们可以反转子字符串 $$$s_{1\ldots 3}$$$,得到字符串 001。我们可以执行两次 $$$1$$$ 操作来输入 00。然后我们执行$$$2$$$操作将手指移动到按钮 1。最后,我们执行一次$$$1$$$操作来输入 1,得到最终的字符串 001 仅使用 $$$4$$$ 操作。
在第五个测试用例中,我们可以反转子字符串 $$$s_{2\ldots 3}$$$,得到字符串 11001。字符串的成本是 $$$8$$$,因为我们可以执行以下操作序列:
- 执行$$$2$$$操作将手指移至按钮 1.
- 执行 $$$1$$$ 操作两次以键入 11.
- 执行$$$2$$$操作将手指移至按钮 0.
- 执行 $$$1$$$ 操作两次以键入 00.
- 执行$$$2$$$操作将手指移至按钮 1.
- 执行一次 $$$1$$$ 操作来输入 1.
在第六个测试用例中,我们可以反转子字符串 $$$s_{5\ldots 17}$$$,得到字符串 1101111011001001000。可以证明,输入二进制字符串所需的最少运算次数为$$$29$$$。