← 返回题目列表

Codeforces · 2176/B

B. 最佳班次

中文机器翻译题面 查看原题

给定一个二进制字符串 $$$s_1s_2 \ldots s_n$$$,其中至少包含一个 1。您想要获得相同长度的二进制字符串,仅包含 1s。为此,您可以多次执行以下操作:

选择一个数字 $$$d$$$ ($$$1 \le d \le n$$$) 并将字符串 $$$t$$$ 视为字符串 $$$s$$$ 循环右移 $$$d$$$,或者更正式地说,$$$t = s_{n - d + 1} \ldots s_{n}s_{1} \ldots s_{n - d}$$$。之后,对于 $$$t_j = 1$$$ 的所有 $$$j$$$,执行 $$$s_j := 1$$$。所描述的操作需要 $$$d$$$ 硬币,其中 $$$d$$$ 是所选的班次金额。

请注意,字符串 $$$s$$$ 中的位置 $$$j$$$(最初 $$$s_j=1$$$)仍等于 $$$1$$$,即使 $$$t_j=0$$$ 也是如此。

您需要确定可以花费的最小硬币数量,以便字符串 $$$s$$$ 仅包含 所有操作后 1秒。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。

每个测试用例的第一行包含数字 $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — 给定二进制字符串的大小。

每个测试用例的第二行包含一个长度为 $$$n$$$ 的二进制字符串,其中每个元素是 0 or 1.

保证每个字符串中至少有一个字符等于 1.

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

输出

对于每个测试用例,输出答案 - 使字符串中的所有字符等于的最小可能数量的硬币 1.

示例

输入
复制

5
1
1
3
101
4
0110
11
10101010100
2
11

输出
复制

0
1
2
2
0

注意

考虑第三个示例,其中 $$$s =$$$ "0110"。在这种情况下,最好选择 $$$d = 2$$$,然后 $$$t =$$$ "1001"。之后,在 $$$j = 1$$$ 和 $$$j = 4$$$ 位置,$$$s_j$$$ 将被替换为 1,从而得到全由 1 组成的字符串 $$$s$$$。请注意,此操作的成本为 $$$d = 2$$$。