Hidden Password

After a successful internship, Bytholomew was hired as a senior cyber-security expert. To lead by example, he decided to finally follow his own advice and use two different passwords, one for his e-mail and one for the Facepalm social media account. Remembering two passwords proved too much for him. He also could not simply write the passwords down somewhere, since that would go against another of his recommendations. As a security expert, he knew exactly what to do. He chose his favorite integer $d > 0$ and wrote both passwords encoded with a Caesar cipher with key $d$.

Pleased with his work, he looked at his notes, and the horrible truth dawned on him: after encoding, the first (e-mail) password had become exactly the second (Facepalm) password, and the second one had turned into the first. "Holy moly!" exclaimed Bytholomew, and there was nothing more to say.

Now you too can become a security expert. Knowing the first of Bytholomew's passwords, guess the second one, if possible.

The first line of input contains the number of test cases $z$ ($1 \leq z \leq 20$). The descriptions of the test cases follow.

Each test case is one word, the password, consisting of lowercase English letters, on a separate line. The password has at least $1$ character and at most $200\,000$ characters.

The total number of characters in all passwords does not exceed $1\,000\,000$.

For every given password, guess and output the second one on a separate line. If the second password cannot be determined (either because there is no solution or because there is more than one), output a single word NIE instead.

The Caesar cipher replaces each letter with the one $d$ places down the alphabet, treating the alphabet as cyclic if necessary. For example, with $d = 3$, the letter a is replaced by d, b by e, ..., w becomes z, x becomes a, y becomes b, and z becomes c.