成功完成實習之後，Bytholomew 獲聘做資深網絡安全專家。為咗以身作則，佢決定終於聽自己嘅建議，喺電郵同 Facepalm 社交媒體用兩個唔同嘅密碼。可惜，要記住兩個密碼對佢嚟講實在太難。另外，佢亦唔可以就咁將密碼寫低，因為咁樣會違反佢另一項建議。不過，身為安全專家，Bytholomew 好清楚應該點做。佢揀咗自己最鍾意嘅整數 $d>0$，將兩個密碼用密鑰為 $d$ 嘅凱撒密碼（1）加密之後寫低。

佢滿意噉望住自己嘅成果，再睇吓筆記，先至發現一個可怕嘅事實：加密之後，第一個（電郵）密碼竟然完全變咗第二個（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。