CF2176B.Optimal Shifts

You are given a binary string $s_1s_2 \ldots s_n$, containing at least one 1. You want to obtain a binary string of the same length, consisting only of 1s. To do this, you can perform the following operation any number of times:

Choose a number $d$ ($1 \le d \le n$) and consider the string $t$ as a cyclic right shift of the string $s$ by $d$, or, more formally, $t = s_{n - d + 1} \ldots s_{n}s_{1} \ldots s_{n - d}$. After that, for all $j$ for which $t_j = 1$, perform $s_j := 1$. The described operation costs $d$ coins, where $d$ is the chosen shift amount.

Note that the positions $j$ in the string $s$, where initially $s_j=1$, remain equal to $1$ even if $t_j=0$.

You need to determine the minimum number of coins that can be spent so that the string $s$ consists only of 1s after all operations.

给你一个二进制字符串 $s_1s_2 \ldots s_n$，其中至少包含一个 1。你的目标是通过若干次操作，将该字符串变为一个长度相同、且全部由 1 组成的二进制字符串。

每次操作可执行如下步骤：

• 选择一个整数 $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（即执行赋值 $s_j := 1$）。

该操作的代价为 $d$ 枚金币，其中 $d$ 即所选的移动位数。

注意：对于初始时 $s_j = 1$ 的位置 $j$，无论后续操作中 $t_j$ 是否为 0，其值始终维持为 1。

你需要求出使得最终字符串 $s$ 全为 1 所需花费的最少金币总数。

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows.

The first line of each test case contains the number $n$ ($1 \le n \le 2 \cdot 10^5$) — the size of the given binary string.

The second line of each test case contains a binary string of length $n$, each element of which is either 0 or 1.

It is guaranteed that at least one character in each string is equal to 1.

It is guaranteed that the sum of $n$ across all test cases does not exceed $2 \cdot 10^5$.

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$（$1 \le t \le 10^4$）。随后是各测试用例的描述。

每个测试用例的第一行包含一个整数 $n$（$1 \le n \le 2 \cdot 10^5$）—— 给定二进制字符串的长度。

每个测试用例的第二行包含一个长度为 $n$ 的二进制字符串，其中每个字符均为 0 或 1。

保证每个字符串中至少有一个字符为 1。

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

For each test case, output the answer to it — the minimum possible number of coins that you can spend to make all characters in the string equal to 1.

对于每个测试用例，输出其答案——即让字符串中所有字符都变为 1 所需花费的最少硬币数。

Consider the third example, where $s = $ "0110". In this case, it is optimal to choose $d = 2$, then $t = $ "1001". After that, at positions $j = 1$ and $j = 4$, $s_j$ will be replaced with 1, resulting in the string $s$ consisting of all ones. Note that the cost of this operation is $d = 2$.

考虑第三个例子，其中 $s = $ "0110"。此时选择 $d = 2$ 是最优的，于是 $t = $ "1001"。随后，在位置 $j = 1$ 和 $j = 4$ 处，$s_j$ 将被替换为 1，最终得到全为 1 的字符串 $s$。注意，该操作的代价为 $d = 2$。