在成功完成實習後，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。