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 1 s. 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 1 s 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).