Setelah menjalani magang dengan sukses, Bytholomew dipekerjakan sebagai pakar senior keamanan siber. Untuk memberi teladan, akhirnya ia memutuskan mengikuti sarannya sendiri dan menggunakan dua kata sandi berbeda untuk surelnya dan untuk media sosial Facepalm. Sayangnya, mengingat dua kata sandi ternyata terlalu sulit baginya. Selain itu, ia tidak bisa begitu saja menuliskan kata sandi tersebut di suatu tempat, karena hal itu bertentangan dengan sarannya yang lain. Namun, sebagai pakar keamanan, Bytholomew tahu persis apa yang harus dilakukan. Ia memilih bilangan bulat favoritnya $d>0$ dan menuliskan kedua kata sandi setelah dienkripsi dengan sandi Caesar (1) menggunakan kunci $d$.

Puas dengan hasil pekerjaannya, ia melihat catatannya dan menyadari kenyataan mengerikan: setelah dienkripsi, kata sandi pertama (surel) menjadi persis kata sandi kedua (Facepalm), sedangkan kata sandi kedua berubah menjadi yang pertama. “Astaga!” seru Bytholomew, karena tidak ada lagi yang bisa dikatakan.

Sekarang Anda juga dapat menjadi pakar keamanan: dengan mengetahui kata sandi pertama Bytholomew, tebak kata sandi kedua, jika memungkinkan.

Masukan

Baris pertama masukan berisi jumlah kasus uji $z$ ($1 \le z \le 20$). Berikutnya diberikan deskripsi kasus-kasus uji.

Setiap kasus uji berupa satu kata — kata sandi — yang terdiri atas huruf kecil bahasa Inggris, pada baris tersendiri. Kata sandi memiliki sedikitnya $1$ karakter dan paling banyak $200\,000$ karakter.

Jumlah seluruh karakter dalam semua kata sandi tidak melebihi $1\,000\,000$.

Keluaran

Untuk setiap kata sandi yang diberikan, tebak dan keluarkan kata sandi kedua pada baris tersendiri. Jika kata sandi kedua tidak dapat ditentukan (karena tidak ada solusi atau ada lebih dari satu solusi), keluarkan satu kata NIE sebagai gantinya.

Contoh

Masukan 1

1
cnffjbeq

Keluaran 1

password

(1) Sandi Caesar mengganti setiap huruf dengan huruf yang terletak $d$ posisi setelahnya dalam alfabet, dengan menganggap alfabet melingkar jika diperlukan. Misalnya, untuk $d=3$, huruf a diganti dengan d, b dengan e, …, w menjadi z, x menjadi a, y menjadi b, dan z menjadi c.