Durante un inventario en el Museo de los azucareros del centro, se encontró una caja de cintas con números escritos. Uno de ellos sugirió que una de las cintas contenía una Gran Identidad: una igualdad de la forma ~a = a~, donde ~a~ es un número natural. Además, el registro del número ~a~ a la izquierda del signo de igual no contiene ceros iniciales, mientras que el de la derecha sí puede comenzar con un cero.

Con el tiempo, el signo de igual se ha borrado y ahora solo queda una secuencia de números en la cinta. Pedro el azucarero afirma que la identidad se puede restaurar si se coloca un signo de igual en algún lugar de la secuencia encontrada.

Escribe un programa que determine si es posible restaurar la Gran Identidad en cada una de las cintas encontradas.

Entrada

• En la primera línea de la entrada estándar, se introduce un número natural ~T~: la cantidad de tiras.
• En las siguientes ~T~ líneas, se introduce una cadena ~S~ compuesta únicamente por dígitos decimales. Se garantiza que ninguna cadena comienza con 0.

Salida

En la salida estándar, el programa debe imprimir ~T~ líneas. La línea i-ésima contiene la posición del dígito después del cual debe colocarse el signo de igual para obtener una identidad correcta, o el número ~-1~ si esto no es posible. Las posiciones se numeran desde el 1.

Restricciones

• ~1 \leq T \leq 10~
• ~1 \leq~ ~longitud~ ~de~ ~S~ ~\leq 4 \cdot 10^5~

Ejemplo de Entrada

3
123123
123122
120012

Ejemplo de Salida

3
-1
2