Te dan una cadena consistente de caracteres ~0~ y ~1~.

Debes eliminar varios (posiblemente cero) caracteres de el inicio de la cadena, y luego varios (posiblemente cero) caracteres del final de la cadena. La cadena puede quedarse vacía después de las eliminaciones. El costo de la eliminación es el máximo de los dos siguientes valores:

• El número de caracteres ~0~ que queden en la cadena;
• El número de caracteres ~1~ eliminados de la cadena.

¿Cuál es el mínimo costo de eliminación que puede ser alcanzado?

Entrada

La primera línea contiene un entero ~t~ (~1 \le t \le 10^4~) el número de casos de prueba.

Cada caso de prueba consiste de una línea conteniendo una cadena ~s~ (~1 \le |s| \le 2*10^5~), formada de caracteres ~0~ y/o ~1~.

El largo total de las cadenas ~s~ en todos los casos de prueba no excederá ~2* 10^5~.

Salida

Para cada caso de prueba, imprime un entero - el mínimo costo de eliminación que puede ser alcanzado.

Subtareas

• Subtarea 1 (La suma de las ~|s| \le 100~): 30 pts.
• Subtarea 2 (La suma de las ~|s| \le 1000~): 50 pts.
• Subtarea 3 (Sin restricciones adicionales): 20 pts.

Ejemplos

Entrada de ejemplo

5
101110110
1001001001001
0000111111
00000
1111

Salida de ejemplo

1
3
0   
0
0

Explicación ejemplo

Considere los casos de prueba de ejemplo:

1. En el primer caso de prueba, es posible eliminar dos caracteres de el inicio y un carácter de el final. Solo un ~1~ es eliminado, solo un ~0~ queda, por lo que el costo es ~1~;
2. En el segundo caso de prueba, es posible eliminar tres caracteres del inicio y seis caracteres del final. Dos caracteres ~0~ quedan, tres caracteres ~1~ son eliminados, por lo que el costo es ~3~;
3. En el tercer caso de prueba, es óptimo eliminar cuatro caracteres del inicio;
4. En el cuarto caso de prueba, es óptimo eliminar la cadena completa;
5. En el quinto caso de prueba, es óptimo dejar la cadena como está.