Dado un entero positivo ~x~ representado como una cadena de dígitos, tu tarea es encontrar el menor entero positivo ~y~ tal que: $$\displaystyle y + \text{reverse}(y) = x$$ donde ~\text{reverse}(y)~ es el entero obtenido al escribir los dígitos de ~y~ en orden inverso.

El número ~y~ no puede tener ceros a la izquierda. Al calcular ~\text{reverse}(y)~, los ceros que queden al inicio se ignoran al interpretar el resultado como un entero.

Si no existe ningún entero ~y~ que cumpla la condición, imprime ~-1~.

Entrada

Cada archivo de entrada contiene múltiples casos de prueba. La primera línea contiene el número de casos de prueba ~t~ (~1 \le t \le 10~). A continuación, se presenta la descripción de cada caso de prueba.

La primera línea de cada caso de prueba contiene una cadena de dígitos que representa el entero ~x~ (~1 \le |x| \le 10^6~, donde ~|x|~ denota la longitud de la cadena ~x~).

Se garantiza que ~x~ no contiene ceros a la izquierda.

Salida

Para cada caso de prueba, imprime una línea con el menor entero positivo ~y~ que satisfaga la condición. Si no existe ningún entero ~y~ que cumpla la condición, imprime ~-1~.

Subtareas

Esta tarea está compuesta por ~4~ subtareas.

Los puntos de una subtarea se otorgan solo si se aceptan todos los casos de esa subtarea.

Subtarea	Puntos	Restricciones adicionales	Dependencias
~1~	~19~	~|x| \le 5~.	~-~
~2~	~27~	~|x| \le 50~.	~1~
~3~	~32~	~|x| \le 1000~.	~1, 2~
~4~	~22~	Sin restricciones adicionales.	~1, 2, 3~

Ejemplos

Entrada 1

5
3982
198
121
1017610
1998

Salida 1

1991
99
29
107909
999