A16559 | Majority Wins?

给定一个长度为 $n$ 的二进制字符串 $s$。

你可以对任意长度为 $k$ 的二进制字符串 $g$ 执行如下操作一次：

- 选择一对 $l, r$，满足 $1 \leq l \leq r \leq k$；
- 将字符串 $g$ 的子串 $g_l, \ldots, g_r$ 替换为该子串中出现次数不少于另一字符的某个字符。

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

例如，字符串 010010 可以通过一次花费为 $4$ 的操作（将 1001 替换成 1）变为 010；字符串 1111 可以通过一次花费为 $4$ 的操作（对整个字符串操作）变为 1；字符串 0100 可以通过选取子串 100，将其替换成 0，例如变为 00。

你需要求出将整个字符串 $s$ 变成字符串 1 所需的最小总代价（可以进行任意次操作，也可以不进行），或者判断是否不可能实现。

注：
$^*$ 二进制字符串指仅包含 $0$ 和 $1$ 的字符串。
$^\dagger$ 子串：对于字符串 $g$，字符串 $t$ 是它的子串，当且仅当 $t$ 能从 $g$ 通过删去若干（可以为零或全部）开头和结尾的字符后得到。

每组测试数据包含多组测试用例。第一行包含一个整数 $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$。

对于每个测试用例，如果无法将字符串 $s$ 变成 1，输出 $-1$。否则，输出最小总代价。