题目描述

给定一幅贵重画作，光头强想和他的 $n$ 个朋友分享。他把画挂在了他的房间里，他的 $n$ 个朋友一个接一个地进入房间并离开。每一刻房间里最多只有一个人。也就是说，第一个朋友进入房间，然后是第二个，以此类推。

已知在开始时（在任何朋友进入房间之前）房间里有一幅画。在最后（即第 $n$ 个朋友离开后）画作消失了。消失的具体时间不得而知。

光头强依次询问了他的每个朋友是否在他进入房间时看到了画。每个朋友都回答了以下三个选项中的一个：

没有（编码为 0）； 看到了（编码为 1）； 不记得了（编码为 ?）。

除了小偷以外，所有人都不记得或者说实话。小偷可以说任何话（三种选项中的任何一种）。

光头强无法判断是谁偷了画。他请你找出有多少人根据答案可以被认为是小偷。

输入格式

第一个数 $t((1≤t≤10^4)$ 表示测试数据的组数。

接下来是每组测试数据的描述。

每组测试数据的第一行包含一个字符串 $s$ (长度不超过 $2⋅10^5$) — 描述朋友答案的字符串，其中 $s_i$ 表示第 $i$ 个朋友的答案。字符串中的每个字符均为 0 或 1 或 ?。

实际情况中已经给出了规则。特别地，在回答的基础上，至少有一位朋友会被怀疑窃取了画。

保证整个输入数据集中字符串长度的总和不超过 $2⋅10^5$。

输出格式

输出一个正整数（严格大于零）——可能盗画的人数。

测试样例

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

1
1
2
5
4
1
1
3

样例说明

在第一种情况下，答案是 $1$，因为我们只有一个朋友。

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

在第三种情况下，嫌疑人是第三个和第四个朋友（我们从一开始数）。可以证明没有其他人可能是小偷。

在第四种情况下，我们什么也不知道，所以我们怀疑每个人。