题目描述

Polycarp 买了一幅昂贵的新画，并决定向他的 $n$ 个朋友展示。他把画挂在自己的房间里。$n$ 个朋友依次一个接一个地进出房间。任意时刻房间里最多只有一个人。换句话说，第一个朋友先进入并离开，然后是第二个朋友，依此类推。

已知在一开始（朋友们还未参观时）房间里挂着画。在最后（第 $n$ 个朋友参观后）发现画已经不见了。但画究竟是在什么时候消失的——并没有相关信息。

Polycarp 逐个询问了他的朋友。他问每个人在进入房间时是否看到画。每个朋友的回答有三种：

• 没有（用 0 编码）；
• 有（用 1 编码）；
• 不记得了（用 ? 编码）。

除了小偷之外，其他人要么不记得，要么说了实话。小偷可以说任意答案（三种都可以）。

Polycarp 无法确定谁是小偷。他请你根据回答，找出有可能是小偷的人数。

输入格式

第一行为整数 $t$（$1 \le t \le 10^4$），表示测试用例的数量。

接下来是每个测试用例的描述。

每个测试用例的第一行包含一个字符串 $s$（长度不超过 $2 \cdot 10^5$），表示朋友们的回答，其中 $s_i$ 表示第 $i$ 个朋友的回答。字符串中的每个字符都是 0、1 或 ?。

实际情况符合题目描述的规律。特别地，根据回答，至少有一个人可以被怀疑是小偷。

保证所有测试用例中字符串长度之和不超过 $2 \cdot 10^5$。

输出格式

输出一个正整数（严格大于零），表示根据所给数据，有多少人可能是小偷。

说明/提示

在第一个样例中，答案是 $1$，因为只有 $1$ 个朋友。

第二个样例与第一个类似。

在第三个样例中，嫌疑人是第三和第四个朋友（从 1 开始计数）。可以证明没有其他人可能是小偷。

在第四个样例中，我们完全不知道情况，因此所有人都是嫌疑人。

由 ChatGPT 4.1 翻译

样例

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

1
1
2
5
4
1
1
3