CF2189E.Majority Wins?

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.

给你一个长度为 $n$ 的二进制字符串$^{\text{∗}}$ $s$。

对一个长度为 $k$ 的二进制字符串 $g$，一次操作可执行如下步骤：

• 选择满足 $1 \leq l \leq r \leq k$ 的下标 $l, r$；

• 将字符串 $g$ 的子串$^{\text{†}}$ $g_l, \ldots, g_r$ 替换为该子串中出现次数不少于另一字符的某个字符（即：若子串中 0 的个数 $\geq$ 1 的个数，则替换为 0；否则替换为 1）。

该操作的代价为 $r-l+1$。

例如，字符串 010010 可通过一次代价为 $4$ 的操作变为 010：将子串 1001 替换为 1；字符串 1111 可通过对整个字符串执行一次代价为 $4$ 的操作变为 1；字符串 0100 可例如通过选取子串 100 并将其替换为 0 而变为 00。

你需要求出将整个字符串 $s$ 变为字符串 1 所需的最小总代价（允许执行若干次（包括零次）操作），或判断这是不可能的。

$^{\text{∗}}$二进制字符串是指仅由字符 $0$ 和 $1$ 组成的字符串。

$^{\text{†}}$若字符串 $t$ 可通过从字符串 $g$ 的开头删除若干（可能为零或全部）字符、并从结尾删除若干（可能为零或全部）字符而得到，则称 $t$ 是 $g$ 的子串。

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

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$（$1 \le t \le 10^4$）。随后是各测试用例的描述。

每个测试用例的第一行包含一个整数 $n$（$1 \leq n \leq 5 \cdot 10^5$）—— 二进制字符串的长度。

每个测试用例的第二行包含一个长度为 $n$ 的字符串，由字符 0 和 1 组成 —— 字符串 $s$。

保证所有测试用例的 $n$ 之和不超过 $5 \cdot 10^5$。

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

对于每个测试用例，若无法得到字符串 1，则输出 $-1$；否则，输出最小代价。

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.

在第一个测试用例中，无法得到字符串 1，因为唯一可能的操作（$l = r = 1$）不会改变原字符串。

在第二个测试用例中，字符串初始即为 1，因此答案为 0。

在第四个测试用例中，可以对整个字符串执行一次操作，将其替换为 1。该操作的代价为 $2$。可以证明，不存在代价更低的方式得到字符串 1。