给你一个二进制字符串$$$^{\text{*}}$$$ $$$s$$$,长度为$$$n$$$。
在一个长度为 $$$k$$$ 的二进制字符串 $$$g$$$ 的操作中,您可以执行以下操作:
- 选择一些 $$$l, r$$$ 使得 $$$1 \leq l \leq r \leq k$$$;
- 将字符串 $$$g$$$ 的子字符串 $$$^{\text{†}}$$$ $$$g_l, \ldots, g_r$$$ 替换为 一 字符在此子字符串中出现的次数至少与其他字符相同。
此类操作的成本将等于 $$$r-l+1$$$。
例如,字符串 010010 可以转化为 010 在一次操作中替换子字符串,成本为 $$$4$$$ 1001 与 1;字符串 1111 可以转化为 1 通过对整个字符串执行成本为 $$$4$$$ 的操作,并且该字符串 例如, 0100 可以转换为 00 通过获取子字符串 100.
你需要找到将整个字符串 $$$s$$$ 转换为字符串的最小成本 1,使用多个(可能没有)操作,或确定这是不可能的。
$$$^{\text{*}}$$$二进制字符串是仅由字符 $$$0$$$ 和 $$$1$$$ 组成的字符串。
$$$^{\text{†}}$$$ 字符串 $$$t$$$ 是字符串 $$$g$$$ 的子字符串,如果 $$$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$$$。
输出
对于每个测试用例,如果无法获取字符串 1,输出$$$-1$$$。否则,输出最小成本。
示例
输入复制
7101120021030108001110006100100
输出复制
-10-12497
注意
在第一个测试用例中,无法获得 1,因为唯一可能的操作 ($$$l = r = 1$$$) 不会更改字符串。
在第二个测试用例中,字符串已经是 1 最初,所以答案是 0.
在第四个测试用例中,可以对整个字符串执行操作,将其替换为 1。此操作的成本为 $$$2$$$。可见无法获取字符串 1 成本更低。