在成功完成实习后，Bytholomew 被聘为一名高级网络安全专家。为了以身作则，他决定听从自己的建议，为他的电子邮件和 Facepalm 社交媒体账户使用两个不同的密码。不幸的是，记住两个密码对他来说太难了。此外，他不能直接把密码写在什么地方，因为这违背了他自己的另一条建议。但作为一名安全专家，Bytholomew 知道该怎么做。他选择了他最喜欢的整数 $d > 0$，并将两个密码都用凯撒密码（Caesar cipher）进行了加密，密钥为 $d$。

他对自己的工作感到满意，但当他查看笔记时，一个可怕的事实浮现在他脑海中：加密后，第一个（电子邮件）密码竟然变成了第二个（Facepalm）密码，而第二个密码变成了第一个密码。“天哪！”Bytholomew 惊呼道，因为他无话可说。

现在你也可以成为一名安全专家——已知 Bytholomew 的第一个密码，请尝试推测出第二个密码（如果可能的话）。

输入格式

输入的第一行包含测试用例的数量 $z$ ($1 \le z \le 20$)。接下来是各测试用例的描述。

每个测试用例包含一个单词（即密码），由小写英文字母组成，占一行。密码长度至少为 1 个字符，最多为 200,000 个字符。

所有密码的总字符数不超过 1,000,000。

输出格式

对于给定的每个密码，请推测并输出第二个密码，占一行。如果无法确定第二个密码（无论是由于无解还是存在多个解），则输出单词 NIE。

样例

输入 1

1
cnffjbeq

输出 1

password

说明

凯撒密码是指将每个字母替换为字母表中其后第 $d$ 位的字母，必要时将字母表视为循环的。例如，当 $d = 3$ 时，字母 a 被替换为 d，b 被替换为 e，……，w 变为 z，x 变为 a，y 变为 b，z 变为 c。