Nach einem erfolgreichen Praktikum wurde Bytholomew als leitender Experte für Cybersicherheit eingestellt. Um mit gutem Beispiel voranzugehen, beschloss er, endlich seinem eigenen Rat zu folgen und zwei verschiedene Passwörter für seine E-Mail und das soziale Netzwerk Facepalm zu verwenden. Leider war es zu viel für ihn, sich zwei Passwörter zu merken. Außerdem konnte er die Passwörter nicht einfach irgendwo im Klartext aufschreiben, denn das hätte einer anderen seiner Empfehlungen widersprochen. Doch als Sicherheitsexperte wusste Bytholomew genau, was zu tun war. Er wählte seine Lieblingszahl, eine ganze Zahl $d>0$, und schrieb beide Passwörter mit der Caesar-Verschlüsselung (1) und dem Schlüssel $d$ verschlüsselt auf.

Zufrieden mit seiner Arbeit betrachtete er seine Notizen und erkannte die schreckliche Wahrheit: Nach der Verschlüsselung war das erste Passwort (für E-Mail) genau zum zweiten Passwort (für Facepalm) geworden, und das zweite zum ersten. „Ach du meine Güte!“, rief Bytholomew, denn mehr gab es nicht zu sagen.

Jetzt kannst auch du Sicherheitsexperte werden: Errate, wenn möglich, das zweite Passwort von Bytholomew, wenn du sein erstes kennst.

Eingabe

Die erste Eingabezeile enthält die Anzahl der Testfälle $z$ ($1 \le z \le 20$). Es folgen die Beschreibungen der Testfälle.

Jeder Testfall besteht aus einem Wort — dem Passwort — aus englischen Kleinbuchstaben in einer eigenen Zeile. Das Passwort hat mindestens $1$ und höchstens $200\,000$ Zeichen.

Die Gesamtzahl der Zeichen in allen Passwörtern überschreitet $1\,000\,000$ nicht.

Ausgabe

Errate für jedes gegebene Passwort das zweite und gib es in einer eigenen Zeile aus. Wenn das zweite Passwort nicht eindeutig bestimmt werden kann (weil es keine Lösung oder mehr als eine gibt), gib stattdessen das einzelne Wort NIE aus.

Beispiele

Eingabe 1

1
cnffjbeq

Ausgabe 1

password

(1) Bei der Caesar-Verschlüsselung wird jeder Buchstabe durch den im Alphabet $d$ Stellen weiter hinten stehenden ersetzt; bei Bedarf wird das Alphabet zyklisch betrachtet. Beispielsweise wird für $d=3$ der Buchstabe a durch d ersetzt, b durch e, …, w wird zu z, x zu a, y zu b und z zu c.