Po udanym stażu Bytholomew został zatrudniony jako starszy ekspert do spraw cyberbezpieczeństwa. Chcąc dawać dobry przykład, postanowił wreszcie posłuchać własnej rady i używać dwóch różnych haseł do poczty elektronicznej i do serwisu społecznościowego Facepalm. Niestety zapamiętanie dwóch haseł okazało się dla niego zbyt trudne. Co więcej, nie mógł ich po prostu gdzieś zapisać, ponieważ byłoby to sprzeczne z inną jego rekomendacją. Jednak jako ekspert do spraw bezpieczeństwa Bytholomew doskonale wiedział, co zrobić. Wybrał swoją ulubioną liczbę całkowitą $d>0$ i zapisał oba hasła zaszyfrowane szyfrem Cezara (1) z kluczem $d$.

Zadowolony z pracy spojrzał na notatki i uświadomił sobie straszną prawdę: po zaszyfrowaniu pierwsze hasło (do poczty) stało się dokładnie drugim hasłem (do Facepalma), a drugie zmieniło się w pierwsze. „O rety!” — wykrzyknął Bytholomew, bo nic więcej nie dało się powiedzieć.

Teraz i Ty możesz zostać ekspertem do spraw bezpieczeństwa — znając pierwsze hasło Bytholomewa, odgadnij drugie, o ile to możliwe.

Wejście

Pierwszy wiersz wejścia zawiera liczbę przypadków testowych $z$ ($1 \le z \le 20$). Dalej następują opisy przypadków testowych.

Każdy przypadek testowy to jedno słowo — hasło — złożone z małych liter alfabetu angielskiego, podane w osobnym wierszu. Hasło ma co najmniej $1$ znak i co najwyżej $200\,000$ znaków.

Łączna liczba znaków we wszystkich hasłach nie przekracza $1\,000\,000$.

Wyjście

Dla każdego podanego hasła odgadnij drugie i wypisz je w osobnym wierszu. Jeżeli nie można jednoznacznie ustalić drugiego hasła (ponieważ nie ma rozwiązania albo jest ich więcej niż jedno), zamiast niego wypisz jedno słowo NIE.

Przykład

Wejście 1

1
cnffjbeq

Wyjście 1

password

(1) Szyfr Cezara polega na zastąpieniu każdej litery literą znajdującą się o $d$ pozycji dalej w alfabecie, traktowanym w razie potrzeby cyklicznie. Na przykład dla $d=3$ litera a jest zastępowana przez d, b przez e, …, w przez z, x przez a, y przez b, a z przez c.