Après un stage réussi, Bytholomew a été embauché comme expert senior en cybersécurité. Pour montrer l’exemple, il a décidé de suivre enfin son propre conseil et d’utiliser deux mots de passe différents pour son courrier électronique et pour le réseau social Facepalm. Malheureusement, retenir deux mots de passe s’est avéré trop difficile pour lui. De plus, il ne pouvait pas simplement les écrire quelque part en clair, car cela irait à l’encontre d’une autre de ses recommandations. Mais, en tant qu’expert en sécurité, Bytholomew savait exactement quoi faire. Il a choisi son entier préféré $d>0$ et a noté les deux mots de passe chiffrés avec le chiffre de César (1) de clé $d$.

Satisfait de son travail, il a regardé ses notes et a découvert l’horrible vérité : après le chiffrement, le premier mot de passe (du courrier électronique) était devenu exactement le second (de Facepalm), tandis que le second était devenu le premier. « Nom d’un chien ! », s’est exclamé Bytholomew, car il n’y avait rien d’autre à dire.

Vous pouvez maintenant devenir vous aussi un expert en sécurité : connaissant le premier mot de passe de Bytholomew, devinez le second, si possible.

Entrée

La première ligne de l’entrée contient le nombre de cas de test $z$ ($1 \le z \le 20$). Les descriptions des cas de test suivent.

Chaque cas de test est un mot — le mot de passe — composé de lettres minuscules de l’alphabet anglais, sur une ligne distincte. Le mot de passe contient au moins $1$ caractère et au plus $200\,000$ caractères.

Le nombre total de caractères dans tous les mots de passe ne dépasse pas $1\,000\,000$.

Sortie

Pour chaque mot de passe donné, devinez et affichez le second sur une ligne distincte. Si le second mot de passe ne peut pas être déterminé (parce qu’il n’existe aucune solution ou qu’il en existe plusieurs), affichez à la place le seul mot NIE.

Exemples

Entrée 1

1
cnffjbeq

Sortie 1

password

(1) Le chiffre de César consiste à remplacer chaque lettre par celle située $d$ positions plus loin dans l’alphabet, en considérant celui-ci comme cyclique si nécessaire. Par exemple, pour $d=3$, la lettre a est remplacée par d, b par e, …, w devient z, x devient a, y devient b et z devient c.