Após um estágio bem-sucedido, Bytholomew foi contratado como especialista sênior em cibersegurança. Para dar o exemplo, decidiu finalmente seguir seu próprio conselho e usar duas senhas diferentes para seu e-mail e para a rede social Facepalm. Infelizmente, lembrar duas senhas foi demais para ele. Além disso, não podia simplesmente anotá-las em algum lugar, pois isso contrariaria outra de suas recomendações. Mas, sendo um especialista em segurança, Bytholomew sabia exatamente o que fazer. Escolheu seu inteiro favorito $d>0$ e anotou ambas as senhas codificadas com a cifra de César (1) de chave $d$.

Satisfeito com seu trabalho, olhou suas anotações e percebeu a terrível verdade: após a codificação, a primeira senha (do e-mail) se tornou exatamente a segunda (do Facepalm), enquanto a segunda se transformou na primeira. “Minha nossa!”, exclamou Bytholomew, pois não havia mais nada a dizer.

Agora você também pode se tornar um especialista em segurança: sabendo a primeira senha de Bytholomew, descubra a segunda, se possível.

Entrada

A primeira linha da entrada contém o número de casos de teste $z$ ($1 \le z \le 20$). Em seguida vêm as descrições dos casos de teste.

Cada caso de teste é uma palavra — a senha — formada por letras minúsculas do alfabeto inglês, em uma linha separada. A senha tem pelo menos $1$ caractere e no máximo $200\,000$ caracteres.

O número total de caracteres de todas as senhas não excede $1\,000\,000$.

Saída

Para cada senha fornecida, descubra e imprima a segunda em uma linha separada. Se não for possível determinar a segunda senha (porque não há solução ou porque há mais de uma), imprima em seu lugar a única palavra NIE.

Exemplos

Entrada 1

1
cnffjbeq

Saída 1

password

(1) A cifra de César consiste em substituir cada letra pela que está $d$ posições à frente no alfabeto, tratando-o como cíclico quando necessário. Por exemplo, para $d=3$, a letra a é substituída por d, b por e, …, w muda para z, x para a, y para b e z para c.