B. Optimal Shifts

时间限制：每测试点1.5秒内存限制：每测试点256 MB

问题描述

给定一个二进制字符串 $s_1 s_2 \dots s_n$ ，其中至少包含一个 1。你希望得到一个相同长度的、仅由 1 组成的二进制字符串。为此，你可以执行任意次数的以下操作：

选择一个数字 $d$ （ $1 \le d \le n$ ），并将字符串 $t$ 视为字符串 $s$ 循环右移 $d$ 位的结果。更形式化地说， $t = s_{n-d+1} \dots s_n s_1 \dots s_{n-d}$ 。之后，对于所有满足 $t_j = 1$ 的 $j$ ，执行 $s_j := 1$ 。该操作花费 $d$ 个硬币，其中 $d$ 是你选择的移位量。

请注意，字符串 $s$ 中最初满足 $s_j = 1$ 的位置 $j$ ，即使在 $t_j = 0$ 的情况下，也会保持为 1。

你需要确定在所有操作之后，为了使字符串 $s$ 仅由 1 组成，可以花费的最小硬币数量。

输入格式

每个测试包含多个测试用例。第一行包含测试用例的数量 $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$ 。

输出格式

对于每个测试用例，输出其答案——为了使字符串中的所有字符都变为 1，你可以花费的最小可能的硬币数量。

样例输入

5
1
1
3
101
4
0110
11
10101010100
2
11

样例输出

样例说明

考虑第三个样例，其中 $s =$ "0110"。在这种情况下，最优方案是选择 $d = 2$ ，那么 $t = $ "1001"。之后，在位置 $j=1$ 和 $j=4$ 处， $s_j$ 将被替换为 1，从而使字符串 $s$ 全部由 1 组成。请注意，此操作的花费是 $d = 2$ 。