После успешной стажировки 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.