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

Samples

5
1
1
3
101
4
0110
11
10101010100
2
11

0
1
2
2
0