给定一个二进制字符串 $$$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.
示例
输入复制
5113101401101110101010100211
输出复制
01220
注意
考虑第三个示例,其中 $$$s =$$$ "0110"。在这种情况下,最好选择 $$$d = 2$$$,然后 $$$t =$$$ "1001"。之后,在 $$$j = 1$$$ 和 $$$j = 4$$$ 位置,$$$s_j$$$ 将被替换为 1,从而得到全由 1 组成的字符串 $$$s$$$。请注意,此操作的成本为 $$$d = 2$$$。