CF1675C.Detective Task

Polycarp bought a new expensive painting and decided to show it to his $n$ friends. He hung it in his room. $n$ of his friends entered and exited there one by one. At one moment there was no more than one person in the room. In other words, the first friend entered and left first, then the second, and so on.

It is known that at the beginning (before visiting friends) a picture hung in the room. At the end (after the $n$-th friend) it turned out that it disappeared. At what exact moment it disappeared — there is no information.

Polycarp asked his friends one by one. He asked each one if there was a picture when he entered the room. Each friend answered one of three:

• no (response encoded with 0);
• yes (response encoded as 1);
• can't remember (response is encoded with ?).

Everyone except the thief either doesn't remember or told the truth. The thief can say anything (any of the three options).

Polycarp cannot understand who the thief is. He asks you to find out the number of those who can be considered a thief according to the answers.

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

已知：在朋友们开始参观之前（即初始时刻），画作确实在房间里；而在第 $n$ 位朋友离开之后（即最终时刻），画作却消失了。但画作究竟在哪个确切时刻消失——我们对此一无所知。

Polycarp 逐个询问了他的朋友们：当他们进入房间时，画作是否还在？每位朋友的回答为以下三种之一：

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

除小偷外，其余所有人要么如实回答，要么回答“记不清了”。而小偷则可以任意作答（即可以回答 0、1 或 ? 中的任意一个）。

Polycarp 无法判断谁是小偷。他请你帮忙计算：根据这些回答，有多少人可能是小偷。

The first number $t$ ($1 \le t \le 10^4$) — the number of test cases in the test.

The following is a description of test cases.

The first line of each test case contains one string $s$ (length does not exceed $2 \cdot 10^5$) — a description of the friends' answers, where $s_i$ indicates the answer of the $i$-th friend. Each character in the string is either 0 or 1 or ?.

The given regularity is described in the actual situation. In particular, on the basis of answers, at least one friend can be suspected of stealing a painting.

It is guaranteed that the sum of string lengths over the entire input data set does not exceed $2 \cdot 10^5$.

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

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

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

所给规律反映了实际情况。特别地，根据这些回答，至少有一名朋友涉嫌窃取画作。

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

Output one positive (strictly more zero) number – the number of people who could steal the picture based on the data shown.

输出一个正数（严格大于零）——根据所给数据，能够偷走这张图片的人数。

In the first case, the answer is $1$ since we had exactly $1$ friend.

The second case is similar to the first.

In the third case, the suspects are the third and fourth friends (we count from one). It can be shown that no one else could be the thief.

In the fourth case, we know absolutely nothing, so we suspect everyone.

第一种情况下，答案为 $1$，因为我们恰好有 $1$ 位朋友。

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

第三种情况下，嫌疑人是第三位和第四位朋友（我们从 $1$ 开始计数）。可以证明，其他人不可能是小偷。

第四种情况下，我们完全一无所知，因此怀疑所有人。