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.

Input

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

Output

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.

Note

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

Optimal Shifts

Examples