考虑在足球比赛结束时简化处罚阶段。
罚球阶段最多包含 $$$10$$$ 踢球,第一队踢第一球,第二队踢第二球,然后第一队踢第三球,依此类推。进球多的球队获胜;如果两队进球数相同,则比赛结果为平局(请注意,这违反了通常的足球规则)。如果一支球队的进球数多于另一队在所有剩余踢球情况下所能达到的进球数,则处罚阶段将停止。例如,如果在第 $$$7$$$ 次踢球后,第一支球队打进了 $$$1$$$ 球,而第二支球队打进了 $$$3$$$ 球,则罚球阶段结束 - 第一支球队无法达到 $$$3$$$ 球。
您知道每次踢球的球员,因此您对每次 $$$10$$$ 踢球都有预测。这些预测由包含 $$$10$$$ 字符的字符串 $$$s$$$ 表示。每个字符可以是 1、0 或 ?。该字符串通过以下方式表示您的预测:
- 如果$$$s_i$$$为1,则第$$$i$$$次踢球肯定会进球;
- 如果$$$s_i$$$为0,则第$$$i$$$次踢球肯定不会进球;
- 如果 $$$s_i$$$ 是 ?,那么第 $$$i$$$ 踢可以向任何方向走。
根据您的预测,您必须计算罚球阶段中可能出现的最小踢球次数(这意味着罚球阶段停止的最早时刻,考虑到所有可能的方式)。请注意,裁判在决定停止处罚阶段时不会考虑任何预测 - 您可能知道某些踢球会/不会得分,但裁判不知道。
输入
第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 1\,000$$$) — 测试用例的数量。
每个测试用例都由包含字符串 $$$s$$$ 的一行表示,该字符串恰好由 $$$10$$$ 字符组成。每个字符可以是 1、0 或 ?。
输出
对于每个测试用例,打印一个整数——罚球阶段的最小可能踢球次数。
示例
输入 #1
4 1?0???1001 1111111111 ?????????? 0100000000
输出 #1
7 10 6 9
注意
考虑示例测试:
在第一个测试用例中,考虑第 $$$1$$$-st、$$$5$$$-th 和 $$$7$$$-th 踢进球得分,并且踢 $$$2$$$、$$$3$$$、$$$4$$$ 和 $$$6$$$ 不成功的情况。那么第一队目前的进球数是$$$3$$$,第二队是$$$0$$$,裁判认为第二队在剩余的踢球中最多可以进$$$2$$$个球。因此,罚球阶段可以在第 $$$7$$$ 次踢球后停止。
在第二个测试用例中,直到所有 $$$10$$$ 踢球完成后,惩罚阶段才会停止。
在第三个测试用例中,如果第一队在前三个踢球中没有进球,而第二队在第$$$6$$$次踢球后,第一队已经进了$$$0$$$个球,第二队已经进了$$$3$$$个球,并且裁判认为第一队在剩余的踢球中最多可以进$$$2$$$个球。因此,罚球阶段可以在第 $$$6$$$ 次踢球后停止。
在第四个测试用例中,即使您可以预测整个处罚阶段,裁判也知道该阶段应该在第 $$$9$$$ 次踢球之后结束。