CF1553C.Penalty

Consider a simplified penalty phase at the end of a football match.

A penalty phase consists of at most $10$ kicks, the first team takes the first kick, the second team takes the second kick, then the first team takes the third kick, and so on. The team that scores more goals wins; if both teams score the same number of goals, the game results in a tie (note that it goes against the usual football rules). The penalty phase is stopped if one team has scored more goals than the other team could reach with all of its remaining kicks. For example, if after the $7$-th kick the first team has scored $1$ goal, and the second team has scored $3$ goals, the penalty phase ends — the first team cannot reach $3$ goals.

You know which player will be taking each kick, so you have your predictions for each of the $10$ kicks. These predictions are represented by a string $s$ consisting of $10$ characters. Each character can either be 1, 0, or ?. This string represents your predictions in the following way:

• if $s_i$ is 1, then the $i$-th kick will definitely score a goal;
• if $s_i$ is 0, then the $i$-th kick definitely won't score a goal;
• if $s_i$ is ?, then the $i$-th kick could go either way.

Based on your predictions, you have to calculate the minimum possible number of kicks there can be in the penalty phase (that means, the earliest moment when the penalty phase is stopped, considering all possible ways it could go). Note that the referee doesn't take into account any predictions when deciding to stop the penalty phase — you may know that some kick will/won't be scored, but the referee doesn't.

考虑一场足球比赛结束时的简化点球阶段。

点球阶段最多包含 $10$ 次射门：第一支队伍先踢第 $1$ 次，第二支队伍踢第 $2$ 次，第一支队伍踢第 $3$ 次，依此类推。进球数多的队伍获胜；若双方进球数相同，则比赛以平局告终（注意：这与常规足球规则不同）。当某支队伍的进球数已超过另一支队伍在剩余所有射门中所能达到的最大可能进球数时，点球阶段即刻终止。例如，若在第 $7$ 次射门后，第一支队伍已进 $1$ 球，而第二支队伍已进 $3$ 球，则点球阶段立即结束——因为第一支队伍即使后续所有射门全部命中，也无法追平或超过 $3$ 球。

你已知每次射门将由哪位球员主罚，因此对全部 $10$ 次射门均有预测。这些预测用一个长度为 $10$ 的字符串 $s$ 表示，其中每个字符为 1、0 或 ?。该字符串按如下方式表示你的预测：

• 若 $s_i$ 为 1，则第 $i$ 次射门必定进球；
• 若 $s_i$ 为 0，则第 $i$ 次射门必定不进球；
• 若 $s_i$ 为 ?，则第 $i$ 次射门可能进球，也可能不进球。

基于你的预测，请计算点球阶段可能发生的最少射门次数（即：在所有可能的发展情形下，点球阶段最早可能在何时终止）。注意：裁判决定是否终止点球阶段时完全不参考任何预测——你或许知道某次射门必然进或必然不进，但裁判并不知情。

The first line contains one integer $t$ ($1 \le t \le 1\,000$) — the number of test cases.

Each test case is represented by one line containing the string $s$, consisting of exactly $10$ characters. Each character is either 1, 0, or ?.

第一行包含一个整数 $t$（$1 \le t \le 1\,000$）—— 测试用例的数量。

每个测试用例由一行字符串 $s$ 表示，该字符串恰好包含 $10$ 个字符。每个字符为 1、0 或 ?。

For each test case, print one integer — the minimum possible number of kicks in the penalty phase.

对于每个测试用例，输出一个整数——点球大战阶段所需的最少踢球次数。

Consider the example test:

In the first test case, consider the situation when the $1$-st, $5$-th and $7$-th kicks score goals, and kicks $2$, $3$, $4$ and $6$ are unsuccessful. Then the current number of goals for the first team is $3$, for the second team is $0$, and the referee sees that the second team can score at most $2$ goals in the remaining kicks. So the penalty phase can be stopped after the $7$-th kick.

In the second test case, the penalty phase won't be stopped until all $10$ kicks are finished.

In the third test case, if the first team doesn't score any of its three first kicks and the second team scores all of its three first kicks, then after the $6$-th kick, the first team has scored $0$ goals and the second team has scored $3$ goals, and the referee sees that the first team can score at most $2$ goals in the remaining kicks. So, the penalty phase can be stopped after the $6$-th kick.

In the fourth test case, even though you can predict the whole penalty phase, the referee understands that the phase should be ended only after the $9$-th kick.

考虑如下样例测试：

在第一个测试用例中，假设第 $1$ 次、第 $5$ 次和第 $7$ 次射门得分，而第 $2$、$3$、$4$ 和 $6$ 次射门未得分。此时，第一支队伍已进 $3$ 球，第二支队伍已进 $0$ 球，裁判判断第二支队伍在剩余射门中最多还能进 $2$ 球。因此，点球阶段可在第 $7$ 次射门后终止。

在第二个测试用例中，点球阶段将持续至全部 $10$ 次射门结束，不会提前终止。

在第三个测试用例中，若第一支队伍前三次射门全部未得分，而第二支队伍前三次射门全部得分，则在第 $6$ 次射门后，第一支队伍得分为 $0$，第二支队伍得分为 $3$，裁判判断第一支队伍在剩余射门中最多还能进 $2$ 球。因此，点球阶段可在第 $6$ 次射门后终止。

在第四个测试用例中，尽管你可以完整预测整个点球过程，但裁判判定该阶段仅能在第 $9$ 次射门后结束。