インターンシップを無事に終えた 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 に変わります。