CF1553C Penalty

考虑一场足球比赛结束时的简化点球阶段。 点球阶段最多包含 $10$ 脚射门，第一支队伍先踢第一脚，第二支队伍踢第二脚，然后第一支队伍踢第三脚，以此类推。进球数多的队伍获胜；如果两队进球数相同，则比赛以平局结束（注意，这与通常的足球规则不同）。如果某一队的进球数已经超过了另一队在剩余所有射门中可能达到的最大进球数，则点球阶段提前结束。例如，如果在第 $7$ 脚射门后，第一队进了 $1$ 个球，第二队进了 $3$ 个球，则点球阶段结束——因为第一队无法追平 $3$ 个进球。 你知道每一脚射门由哪位球员主罚，因此你对每一脚射门都有预测。这些预测用一个长度为 $10$ 的字符串 $s$ 表示。每个字符可以是 $1$、$0$ 或 $?$。该字符串的含义如下： - 如果 $s_i$ 是 $1$，则第 $i$ 脚射门一定进球； - 如果 $s_i$ 是 $0$，则第 $i$ 脚射门一定不进球； - 如果 $s_i$ 是 $?$，则第 $i$ 脚射门可能进球，也可能不进球。 根据你的预测，你需要计算点球阶段可能进行的最少射门数（即考虑所有可能情况，点球阶段最早可以在第几脚射门后结束）。注意，裁判在决定是否提前结束点球阶段时不会考虑你的预测——你可能知道某一脚一定进或不进，但裁判只根据实际可能性判断。

第一行包含一个整数 $t$（$1 \le t \le 1000$）——表示测试用例的数量。 每个测试用例占一行，包含一个长度为 $10$ 的字符串 $s$，每个字符为 $1$、$0$ 或 $?$。

对于每个测试用例，输出一个整数——点球阶段可能进行的最少射门数。

考虑如下示例： 在第一个测试用例中，假设第 $1$、$5$ 和 $7$ 脚射门进球，第 $2$、$3$、$4$ 和 $6$ 脚射门未进球。此时第一队进了 $3$ 个球，第二队进了 $0$ 个球，裁判会发现第二队在剩余射门中最多只能再进 $2$ 个球，因此点球阶段在第 $7$ 脚后就可以结束。 在第二个测试用例中，点球阶段直到 $10$ 脚全部踢完才会结束。 在第三个测试用例中，如果第一队前三脚都未进球，第二队前三脚都进球，那么在第 $6$ 脚后，第一队进球数为 $0$，第二队进球数为 $3$，裁判会发现第一队在剩余射门中最多只能再进 $2$ 个球，因此点球阶段在第 $6$ 脚后就可以结束。 在第四个测试用例中，尽管你能预测整个点球阶段，但裁判会判断点球阶段只能在第 $9$ 脚后才能结束。 由 ChatGPT 4.1 翻译