Tras unas prácticas exitosas, Bytholomew fue contratado como experto sénior en ciberseguridad. Para dar ejemplo, decidió por fin seguir su propio consejo y usar dos contraseñas diferentes para su correo electrónico y para la red social Facepalm. Por desgracia, recordar dos contraseñas resultó demasiado para él. Además, no podía simplemente anotarlas en algún sitio, pues eso iría en contra de otra de sus recomendaciones. Pero, como experto en seguridad, Bytholomew sabía exactamente qué hacer. Eligió su entero favorito $d>0$ y anotó ambas contraseñas codificadas con el cifrado César (1) de clave $d$.

Satisfecho con su trabajo, miró sus notas y descubrió una verdad terrible: tras la codificación, la primera contraseña (del correo electrónico) se había convertido exactamente en la segunda (de Facepalm), y la segunda en la primera. «¡Madre mía!», exclamó Bytholomew, pues no había nada más que decir.

Ahora tú también puedes convertirte en un experto en seguridad: conociendo la primera contraseña de Bytholomew, adivina la segunda, si es posible.

Entrada

La primera línea de la entrada contiene el número de casos de prueba $z$ ($1 \le z \le 20$). A continuación se describen los casos de prueba.

Cada caso de prueba es una palabra —la contraseña— formada por letras minúsculas del alfabeto inglés, en una línea independiente. La contraseña tiene al menos $1$ carácter y como máximo $200\,000$ caracteres.

El número total de caracteres de todas las contraseñas no supera $1\,000\,000$.

Salida

Para cada contraseña dada, adivina e imprime la segunda en una línea independiente. Si no se puede determinar la segunda contraseña (porque no hay solución o porque hay más de una), imprime en su lugar la única palabra NIE.

Ejemplos

Entrada 1

1
cnffjbeq

Salida 1

password

(1) El cifrado César consiste en sustituir cada letra por la que está $d$ posiciones más adelante en el alfabeto, tratándolo como cíclico si es necesario. Por ejemplo, para $d=3$, a se sustituye por d, b por e, …, w cambia a z, x a a, y a b y z a c.