题目描述

C老师买了一幅新的昂贵的画，并决定把它展示给他的 n 个朋友们。他把它挂在他的房间里，他的朋友们一一进出那里，每次房间里只剩下一个人。换句话说，第一个朋友先进入和离开，然后是第二个，以此类推。

一开始（在朋友拜访之前）房间里挂着一张照片，但是最后在 n 个朋友进出后它消失了。它是在什么时候消失的——没有任何信息。

C老师一一问他的朋友。当朋友进入房间时，他问每个人是否有一张照片。每个朋友回答三个答案之一：

否（用 0 表示）； 是（用1 表示）； 不记得了（用 ? 表示）。 除了小偷，其他人都说的真话。小偷可以说任何话（三个选项中的任何一个）。

C老师无法找出小偷是谁。他要求你根据答案侦探出可以被认为是小偷的人数。

输入格式

第一个数字t(1<=t<=100000)每个测试用例的一行包含一个字符串 s(长度小于2*1000000）字符串中的每个字符都是 0 或 1 或 ?，表示朋友的回答。数据保证至少有一个朋友涉嫌偷画。

输出格式

针对每个测试用例，输出可能涉嫌偷画的人数。

输入输出样例

输入数据 1

8
0
1
1110000
?????
1?1??0?0
0?0???
??11
??0??

输出数据 1

1
1
2
5
4
1
1
3

说明 / 提示

样例说明 在第一种情况下，答案是 1，因为只有 1 个朋友。

第二种情况与第一种情况类似。

在第三种情况下，嫌疑人是第三和第四个朋友。可以证明，没有其他人可以成为小偷。

第四种情况，一无所知，所以我们怀疑每个人。

以上是题目，求各位巨佬帮帮本蒟蒻！（必关注）