Після успішного стажування Bytholomew найняли старшим фахівцем із кібербезпеки. Щоб подавати приклад, він нарешті вирішив дослухатися до власної поради й використовувати два різні паролі для електронної пошти та соціальної мережі Facepalm. На жаль, запам’ятати два паролі виявилося для нього надто складно. До того ж він не міг просто записати їх десь відкритим текстом, адже це суперечило б іншій його рекомендації. Але як фахівець із безпеки Bytholomew точно знав, що робити. Він обрав своє улюблене ціле число $d>0$ і записав обидва паролі, зашифрувавши їх шифром Цезаря (1) із ключем $d$.

Задоволений своєю роботою, він поглянув на записи й усвідомив жахливу правду: після шифрування перший пароль (від пошти) став точнісінько другим паролем (від Facepalm), а другий перетворився на перший. «Отакої!» — вигукнув Bytholomew, адже більше не було чого сказати.

Тепер і ви можете стати фахівцем із безпеки: знаючи перший пароль Bytholomew, вгадайте другий, якщо це можливо.

Вхідні дані

Перший рядок вхідних даних містить кількість тестових випадків $z$ ($1 \le z \le 20$). Далі наведено описи тестових випадків.

Кожен тестовий випадок — це одне слово, пароль, що складається з малих літер англійського алфавіту й записане в окремому рядку. Пароль містить щонайменше $1$ і щонайбільше $200\,000$ символів.

Сумарна кількість символів у всіх паролях не перевищує $1\,000\,000$.

Вихідні дані

Для кожного заданого пароля вгадайте другий і виведіть його в окремому рядку. Якщо другий пароль неможливо однозначно визначити (оскільки розв’язку немає або їх більше одного), натомість виведіть єдине слово NIE.

Приклади

Вхідні дані 1

1
cnffjbeq

Вихідні дані 1

password

(1) Шифр Цезаря замінює кожну літеру літерою на $d$ позицій далі в алфавіті, за потреби вважаючи алфавіт циклічним. Наприклад, за $d=3$ літера a замінюється на d, b на e, …, w переходить у z, x в a, y в b, а z у c.