Florencio recuerda de sus tiempos de escolar aquel día que le mostraron por primera vez las palabras palíndromas~^1~. En ese entonces le parecieron sorprendentes. Ya como universitario, parecería que no volvería a toparse con ellas. Sin embargo, mientras realizaba las cuentas de su negocio, notó que el número ~12521~ podría considerarse como un número palíndromo, ya que al revés resulta en el mismo número. Emocionado por su gran descubrimiento se le ocurrió un juego muy interesante. Dado un número ~x~, cual es el número palíndromo mayor o igual que este, más cercano. Más formalmente, debe encontrar un número ~y~ tal que ~x \le y~, siendo ~y~ un número palíndromo.

~^1~Una palabra palíndroma es aquella que se lee igual derecha que al revés. Ej, "ana", "recocer", "reconocer" son palíndromos; "marta", "abanico" no son palíndromas.

Entrada

La primera línea contendrá un número ~t~ (~1 \le t\le 10^3~) la cantidad de casos de prueba.

Cada caso de prueba consistirá en un único número ~x~ de hasta ~10^4~ dígitos.

La suma de los dígitos de los números de todos los casos de prueba no excederá a ~10^4~.

Salida

Para cada caso de prueba debe imprimir único número, el menor número palíndromo mayor o igual que ~x~.

Límites

Para 40 pts.: ~x \le 10^6~

Para 50 pts.: ~x \le 10^{18}~

Para 10 pts.: Sin restricciones adicionales.

Ejemplos

Entrada de ejemplo

6
123465
100
22
999999946456123
154321654321534653215456321487983131321654135
3999999

Salida de ejemplo

124421
101
22
999999949999999
154321654321534653215464512356435123456123451
4000004