← 返回题目列表

Codeforces · 1675/C

C. 侦探任务

中文机器翻译题面 查看原题

波利卡普买了一幅新的昂贵的画,并决定将其展示给他的 $$$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开始数)。可以证明没有其他人是小偷。

在第四个案例中,我们一无所知,所以我们怀疑所有人。