波利卡普买了一幅新的昂贵的画,并决定将其展示给他的 $$$n$$$ 朋友。他把它挂在自己的房间里。他的朋友$$$n$$$一一进出那里。一时间,房间里只剩下一个人了。换句话说,第一个朋友先进入并离开,然后是第二个,依此类推。
据了解,一开始(在拜访朋友之前)房间里挂着一张照片。最后(在第 $$$n$$$ 个朋友之后)结果发现它消失了。它具体是在什么时刻消失的——没有任何信息。
波旅甲一一询问他的朋友们。当他走进房间时,他问每个人是否有一张照片。每个朋友都回答以下三个之一:
- 否(响应编码为 0);
- 是(响应编码为 1);
- 不记得了(响应是用 ? 编码的)。
除了小偷之外,每个人要么不记得,要么说实话。小偷可以说什么(三个选项中的任何一个)。
坡旅甲无法理解小偷是谁。他要求你根据答案找出多少人可以被认为是小偷。
输入
第一个数字 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试中测试用例的数量。
以下是测试用例的描述。
每个测试用例的第一行包含一个字符串$$$s$$$(长度不超过$$$2 \cdot 10^5$$$)——对好友答案的描述,其中$$$s_i$$$表示第$$$i$$$个好友的答案。字符串中的每个字符要么是 0,要么是 1,要么是 ?。
给出的规律是根据实际情况描述的。特别是,根据答案,至少有一个朋友可能涉嫌盗窃一幅画。
保证整个输入数据集的字符串长度总和不超过$$$2 \cdot 10^5$$$。
输出
输出一个正数(严格来说是零)——根据显示的数据可以窃取图片的人数。
示例
输入 #1
8 0 1 1110000 ????? 1?1??0?0 0?0??? ??11 ??0??
输出 #1
1 1 2 5 4 1 1 3
注意
在第一种情况下,答案是 $$$1$$$ 因为我们正好有 $$$1$$$ 朋友。
第二种情况与第一种情况类似。
第三起案件中,犯罪嫌疑人是第三个和第四个朋友(我们从1开始数)。可以证明没有其他人是小偷。
在第四个案例中,我们一无所知,所以我们怀疑所有人。