CF2261A Hey, It's Me, Souvlakity

Souvlakity 和 Kalamakity 正在玩一个新的游戏。 所有从 $1$ 到 $n$ 的整数已经在两名玩家之间分配完毕。分配情况可以用一个长度为 $n$ 的二进制字符串 $s$ 表示，其中 $s_i = 1$ 表示整数 $i$ 分配给了 Souvlakity，而 $s_i = 0$ 表示分配给了 Kalamakity。保证最初 Souvlakity 至少拥有一个整数（即 $s$ 中至少有一个 $1$）。 这个游戏将持续 $10^{100}$ 轮。两名玩家轮流进行操作，Souvlakity 先手。 在每一轮，轮到的玩家必须选择自己拥有的一个整数，并将其给对方。在本题的约束下可以保证这总是可行的。 在所有 $10^{100}$ 轮结束后，Souvlakity 计算自己的得分，得分等于他拥有的整数的区间范围（即他的得分为 $\max(S) - \min(S)$，其中 $S$ 为他最终拥有的所有整数集合）。保证结束时 Souvlakity 至少会拥有一个整数。 Souvlakity 会尽量最大化自己的得分，而 Kalamakity 会尽量最小化 Souvlakity 的得分。如果双方都采取最优策略，Souvlakity 的最终得分是多少？

每个测试点包含多组测试数据。第一行输入一个整数 $t$（$1 \le t \le 100$），表示测试用例的数量。 每个测试用例的第一行包含一个整数 $n$（$2 \le n \le 100$）。 第二行输入一个长度为 $n$ 的二进制字符串 $s$。保证 $s$ 中至少有一个 $\mathtt{1}$。

对于每个测试用例，输出一行一个整数，表示游戏结束后 Souvlakity 的最终得分（如果双方都采取最优策略）。

在第一个样例中，Souvlakity 最初只拥有整数 $2$。在每对连续的回合（Souvlakity 的回合和 Kalamakity 的回合）中，Souvlakity 送出一个整数并收到一个整数，因此，每次 Kalamakity 操作后他所拥有的整数数量与最初一样。因为回合数是偶数，最后一回合是 Kalamakity 操作，所以最后 Souvlakity 只剩下一个整数，得分 $0$。 在第二个样例中，Souvlakity 最初拥有所有 $3$ 个整数。根据同样的推理，最终他依然拥有全部 $3$ 个整数，所以得分为 $3 - 1 = 2$。 由 ChatGPT 5 翻译