Architecture is often the result of friction between two brilliant but opposing minds. Kotori and Umi, lead architects for a new metropolitan promenade, find themselves in a deadlock regarding the pavement's aesthetic direction. The promenade is modeled as a sequence of $n$ cells in a single row.

Some cells have already been paved: some contain Kotori's signature white marble, while others contain Umi's preferred black granite. Many cells remain empty (marked as "?"). Kotori and Umi must now fill the remaining cells one by one.

To ensure total fairness in their collaboration and to prevent any single philosophy from dominating without a struggle, they have agreed to a formal design protocol:

• Kotori and Umi take turns placing a single stone into an empty cell, with Kotori going first.
• Kotori always places a white marble stone, as she believes the beauty of the promenade is measured by its longest contiguous segment of white marbles. She naturally seeks to maximize this length.
• Umi, seeking to provide structural contrast and rhythm, believes that long, uninterrupted white segments are monotonous. She always places a black granite stone, aiming to minimize that same maximum length.

Once a stone is placed, it cannot be moved or replaced. The process continues until all empty cells are filled.

Given the initial state of the promenade, your task is to determine the final "Aesthetic Score" — the length of the longest contiguous segment of white marbles — assuming both architects play optimally to achieve their respective aesthetic goals.

Input

There are multiple test cases. The first line of the input contains an integer $T$ ($1 \le T \le 10^4$) indicating the number of test cases. For each test case:

The first and only line contains a single string $s_1 s_2 \dots s_n$ of length $n$ ($1 \le n \le 10^5$), where:

• 0 represents a cell already containing Kotori's white marble;
• 1 represents a cell already containing Umi's black granite;
• ? represents a currently empty cell.

It is guaranteed that the sum of $n$ over all test cases does not exceed $10^6$.

Output

For each test case, output one line that contains an integer indicating the final score of the game.

Examples

Input 1

6
??
000
111
0??0??0
0?0?0?0
00?00?100?0

Output 1

1
3
0
3
5
5