题目描述

给定一个二进制字符串 $s_1s_2 \ldots s_n$，其中至少包含一个 $1$。你需要将其变为同样长度且全部由 $1$ 组成的二进制字符串。为此，你可以进行如下任意次操作：

选择一个整数 $d$（$1 \le d \le n$），将字符串 $s$ 进行循环右移 $d$ 位得到新字符串 $t$，形式化地表示为：$t = s_{n-d+1} \ldots s_{n} s_1 \ldots s_{n-d}$。之后，对所有 $j$ 满足 $t_j = 1$，执行 $s_j := 1$。该操作的花费为 $d$ 个金币。

注意，原本 $s_j=1$ 的位置即便 $t_j=0$ 也会维持为 $1$。

请你计算将 $s$ 变为全是 $1$ 的字符串所需的最小金币总数。

输入格式

每组测试数据包含多组用例。第一行输入测试用例组数 $t$（$1 \le t \le 10^4$）。接下来每组测试用例如下：

每组测试用例的第一行输入整数 $n$（$1 \le n \le 2 \times 10^5$），表示二进制字符串的长度。

第二行输入一个长度为 $n$ 的仅由 $0$ 和 $1$ 组成的字符串。

保证每个字符串至少包含一个 $1$。

保证所有用例中 $n$ 的总和不超过 $2\times10^5$。

输出格式

对于每个测试用例，输出一个整数，即将所有字符变为 $1$ 所需的最小金币总数。

说明/提示

以第三组样例为例，$s =$ "0110"。此时，最优方案是选择 $d = 2$，则 $t =$ "1001"。这样，第 $j = 1$ 和 $j = 4$ 位置的 $s_j$ 会被置为 $1$，最终字符串 $s$ 全部为 $1$。该操作花费 $d = 2$。

由 ChatGPT 5 翻译

样例

5
1
1
3
101
4
0110
11
10101010100
2
11

0
1
2
2
0