You are given a binary string$$$^{\text{∗}}$$$ $$$s$$$ of length $$$n$$$.

In one operation with a binary string $$$g$$$ of length $$$k$$$, you can do the following:

choose some $$$l, r$$$ such that $$$1 \leq l \leq r \leq k$$$;
replace the substring$$$^{\text{†}}$$$ $$$g_l, \ldots, g_r$$$ of the string $$$g$$$ with one character that appears in this substring at least as many times as the other character.

The cost of such an operation will be equal to $$$r-l+1$$$.

For example, the string 010010 can be transformed into 010 in one operation with a cost of $$$4$$$ by replacing the substring 1001 with 1; the string 1111 can be transformed into 1 by performing an operation with a cost of $$$4$$$ on the entire string, and the string 0100 can be transformed, for example, into 00 by taking the substring 100.

You need to find the minimum cost to transform the entire string $$$s$$$ into the string 1, using several (possibly none) operations, or determine that it is impossible.

$$$^{\text{∗}}$$$A binary string is a string that only consists of characters $$$0$$$ and $$$1$$$.

$$$^{\text{†}}$$$A string $$$t$$$ is a substring of a string $$$g$$$ if $$$t$$$ can be obtained from $$$g$$$ by the deletion of several (possibly, zero or all) characters from the beginning and several (possibly, zero or all) characters from the end.

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 a single integer $$$n$$$ ($$$1 \leq n \leq 5 \cdot 10^5$$$) — the length of the binary string.

The second line of each test case contains a string of length $$$n$$$, consisting of the characters 0 and 1 — the string $$$s$$$.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$5 \cdot 10^5$$$.

Output

For each test case, if it is impossible to obtain the string 1, output $$$-1$$$. Otherwise, output the minimum cost.

Note

In the first test case, it is impossible to obtain 1, since the only possible operation ($$$l = r = 1$$$) does not change the string.

In the second test case, the string is already 1 initially, so the answer is 0.

In the fourth test case, it is possible to perform an operation on the entire string, replacing it with 1. The cost of this operation is $$$2$$$. It can be shown that it is impossible to obtain the string 1 for a lower cost.

Majority Wins?

Examples