Detective Task
Contest: Codeforces Round 787 (Div. 3)
Difficulty rating: 1100
Tags: implementation

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.

Input format:
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$$$.

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

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
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.

Example input:
8
0
1
1110000
?????
1?1??0?0
0?0???
??11
??0??

Example output:
1
1
2
5
4
1
1
3

Editorial:
First, let's note that we will have a transition from $$$1$$$ to $$$0$$$ only once, otherwise it turns out that first the picture disappeared, then it appeared and disappeared back, but we can consider that a friend in the middle, who answered $$$1$$$ lied to us, but this is not true, because even before him the picture disappeared.
So we need to find this transition. Since we can also meet $$$?$$$, we find the index of the leftmost $$$0$$$ (in case of absence, we take $$$n - 1$$$) and mark it as $$$r_0$$$, and the index of rightmost $$$1$$$ (in case of absence, we take $$$0$$$) and mark as $$$l_1$$$. Answer – the number of indices between them (inclusive), because only they could lie. $$$r_0 - l_1 + 1$$$
There could not be a thief to the left of $$$l_1$$$, since either the friend under the index $$$l_1$$$ lied, or the picture was not stolen before $$$l_1$$$. There could not be a thief to the right of $$$r_0$$$, since either the painting had already been stolen in the presence of $$$r_0$$$'s friend, or it was he who lied.