Binary String Game

 There is a binary string 

S$S$. Alice and Bob are playing a game on it.

Each turn, the following happens:

1. Alice selects a 01$01$ subsequence in S$S$ and removes it from S$S$. (a 01$01$ subsequence is a length 2$2$ subsequence whose first character is 0$0$ and second character is 1$1$)
2. Bob selects a 01$01$ subsequence in S$S$ and removes it from S$S$.
3. After both players have moved, the turn is called completed and Alice scores 1$1$ point. Then, the next turn begins.

If either player is unable to move (there isn't any 01$01$ subsequence left in S$S$), that turn ends immediately and the game ends.

Alice tries to maximize her points, while Bob tries to minimize Alice's points. Find how many points Alice would score if both players play optimally.

Input Format

• The first line contains a single integer T$T$ — the number of test cases.
• Each of the next T$T$ lines contains a binary string S$S$.

Output Format

For each test case, output on a new line a single integer — Alice's score when both players play optimally.

Constraints

• 1≤T≤2⋅105$1\le T\le 2\cdot {10}^5$
• The sum of |S|$|S|$ across all tests doesn't exceed 2⋅105$2\cdot {10}^5$

Subtasks

• Subtask 1 (25 Points):
  • The sum of |S|$|S|$ across all tests doesn't exceed 100$100$
• Subtask 2 (25 Points):
  • The sum of |S|$|S|$ across all tests doesn't exceed 1500$1500$
• Subtask 3 (50 Points):
  • No further constraints.

Sample Input 1 

4
01010101
0101
10
01001011

Sample Output 1 

1 
1 
0 
2 

Explanation

In the first example, this is one of the possible outcomes.

Turn 1$1$:

• Alice removes subsequence (1,2)$(1,2)$ from S$S$, so S$S$ becomes 010101.
• Bob removes subsequence (3,6)$(3,6)$ from S$S$, so S$S$ becomes 0110.
• Alice scores one point and the first turn ends.

Turn 2:

• Alice removes subsequence (1,2)$(1,2)$ from S$S$, so S$S$ becomes 10.
• Bob has nothing to do, so the game ends immediately.

Thus, Alice has one point in total.