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.

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 $ .

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.

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 $ .