La arquitectura es a menudo el resultado de la fricción entre dos mentes brillantes pero opuestas. Kotori y Umi, arquitectas principales de un nuevo paseo metropolitano, se encuentran en un punto muerto con respecto a la dirección estética del pavimento. El paseo se modela como una secuencia de $n$ celdas en una sola fila.

Algunas celdas ya han sido pavimentadas: algunas contienen el característico mármol blanco de Kotori, mientras que otras contienen el granito negro preferido de Umi. Muchas celdas permanecen vacías (marcadas como "?"). Kotori y Umi deben ahora llenar las celdas restantes una por una.

Para garantizar una total equidad en su colaboración y evitar que una sola filosofía domine sin oposición, han acordado un protocolo formal de diseño:

• Kotori y Umi se turnan para colocar una sola piedra en una celda vacía, comenzando Kotori primero.
• Kotori siempre coloca una piedra de mármol blanco, ya que cree que la belleza del paseo se mide por su segmento contiguo más largo de mármoles blancos. Naturalmente, busca maximizar esta longitud.
• Umi, buscando proporcionar contraste estructural y ritmo, cree que los segmentos blancos largos e ininterrumpidos son monótonos. Ella siempre coloca una piedra de granito negro, con el objetivo de minimizar esa misma longitud máxima.

Una vez colocada una piedra, no se puede mover ni reemplazar. El proceso continúa hasta que todas las celdas vacías estén llenas.

Dado el estado inicial del paseo, tu tarea es determinar la "Puntuación Estética" final — la longitud del segmento contiguo más largo de mármoles blancos — asumiendo que ambas arquitectas juegan de manera óptima para lograr sus respectivos objetivos estéticos.

Entrada

Hay múltiples casos de prueba. La primera línea de la entrada contiene un entero $T$ ($1 \le T \le 10^4$) que indica el número de casos de prueba. Para cada caso de prueba:

La primera y única línea contiene una sola cadena $s_1 s_2 \dots s_n$ de longitud $n$ ($1 \le n \le 10^5$), donde:

• 0 representa una celda que ya contiene el mármol blanco de Kotori;
• 1 representa una celda que ya contiene el granito negro de Umi;
• ? representa una celda actualmente vacía.

Se garantiza que la suma de $n$ en todos los casos de prueba no supera $10^6$.

Salida

Para cada caso de prueba, imprime una línea que contenga un entero indicando la puntuación final del juego.

Ejemplos

Entrada 1

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

Salida 1

1
3
0
3
5
5