题目描述

考虑在足球比赛结束时简化的罚球阶段。

一个罚球阶段最多包括 $10$ 次踢球，第一队踢第一球，第二队踢第二球，然后第一队踢第三球，依此类推。进球多的球队获胜；如果两支球队的进球数相同，则比赛结

果为平局（请注意，这违反了通常的足球规则）。如果一支球队的进球数超过了另一支球队用剩余的所有踢球所能达到的进球数，那么点球阶段就会停止。例如，如果

在第 $7$ 次踢球后，第一队进了 $1$ 球，第二队进了 $3$ 球，则罚球阶段结束——第一队不能进 $3$ 球。

您知道哪位球员会踢每一脚，因此您可以对 $10$ 次踢中的每一脚进行预测。这些预测由一个由 $10$ 个字符组成的字符串 $s$ 表示。每个字符可以是 $1、0$ 或 $?$。此字

符串以下列方式表示您的预测：

如果 $si$ 为 $1$，则第 $i$ 次踢肯定会进球；

如果 $si$ 为 $0$，那么第 $i$ 次踢球肯定不会进球；

如果 $si$ 是 $?$，那么第 $i$ 个踢球可以是进球也可以是不进球。

根据您的预测，您必须计算罚球阶段的最小可能踢球次数（这意味着罚球阶段停止的最早时刻，考虑所有可能的方式）。请注意，裁判在决定停止罚球阶段时不考

虑任何预测——您可能知道某些踢球会/不会得分，但裁判不会。

输入格式

输入

第一行包含一个整数 $t$ $(1≤t≤10000)$——测试用例的数量。

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

输出格式

输出

对于每个测试用例，打印一个整数——罚球阶段的最小可能踢球次数。

样例

输入

4
1?0???1001
1111111111
??????????
0100000000

输出

7
10
6
9

数据范围与提示

在第一个测试用例中，考虑第 $1$、第 $5$ 和第 $7$ 次踢球得分，第 $2、3、4$ 和 $6$ 次踢球不成功的情况。那么当前第一队的进球数是$3$，第二队的进球数是$0$，裁判看 到

第二队在剩余的踢球中最多可以进$2$球。所以罚球阶段可以在第 $7$ 次踢球后停止。

在第二个测试案例中，直到所有 $10$ 次踢球都完成后，才会停止处罚阶段。

在第三个测试案例中，如果第一队的三个首球都没有得分，而第二队的三个首球都得分，那么在第 $6$ 次踢球后，第一队已经进了 $0$ 球，第二队球队已经进了 $3$ 个

球，裁判认为第一支球队在剩余的踢球中最多可以进 $2$ 个球。因此，罚球阶段可以在第 $6$ 次踢球后停止。

在第四个测试案例中，即使您可以预测整个罚球阶段，但裁判明白该阶段应该在第 $9$ 次踢球后结束。