Sau một kỳ thực tập thành công, Bytholomew được tuyển làm chuyên gia an ninh mạng cấp cao. Để làm gương, cuối cùng anh quyết định nghe theo lời khuyên của chính mình và dùng hai mật khẩu khác nhau cho thư điện tử và mạng xã hội Facepalm. Không may, việc nhớ hai mật khẩu lại quá sức đối với anh. Hơn nữa, anh không thể đơn thuần ghi các mật khẩu ra đâu đó, vì điều này trái với một khuyến nghị khác của anh. Nhưng là chuyên gia bảo mật, Bytholomew biết chính xác phải làm gì. Anh chọn số nguyên yêu thích $d>0$ và ghi lại cả hai mật khẩu sau khi mã hóa bằng mật mã Caesar (1) với khóa $d$.

Hài lòng với công việc của mình, anh nhìn những ghi chép và nhận ra sự thật khủng khiếp: sau khi mã hóa, mật khẩu thứ nhất (của thư điện tử) trở thành đúng mật khẩu thứ hai (của Facepalm), còn mật khẩu thứ hai lại trở thành mật khẩu thứ nhất. “Trời đất ơi!” — Bytholomew thốt lên, vì chẳng còn gì để nói nữa.

Giờ bạn cũng có thể trở thành chuyên gia bảo mật: biết mật khẩu thứ nhất của Bytholomew, hãy đoán mật khẩu thứ hai, nếu có thể.

Dữ liệu vào

Dòng đầu tiên của dữ liệu vào chứa số lượng bộ kiểm thử $z$ ($1 \le z \le 20$). Tiếp theo là mô tả các bộ kiểm thử.

Mỗi bộ kiểm thử là một từ — mật khẩu — gồm các chữ cái tiếng Anh viết thường, nằm trên một dòng riêng. Mật khẩu có ít nhất $1$ ký tự và nhiều nhất $200\,000$ ký tự.

Tổng số ký tự trong tất cả các mật khẩu không vượt quá $1\,000\,000$.

Dữ liệu ra

Với mỗi mật khẩu đã cho, hãy đoán và in mật khẩu thứ hai trên một dòng riêng. Nếu không thể xác định mật khẩu thứ hai (do không có nghiệm hoặc có nhiều hơn một nghiệm), hãy in duy nhất từ NIE thay thế.

Ví dụ

Dữ liệu vào 1

1
cnffjbeq

Dữ liệu ra 1

password

(1) Mật mã Caesar thay mỗi chữ cái bằng chữ cái đứng sau nó $d$ vị trí trong bảng chữ cái, coi bảng chữ cái là tuần hoàn nếu cần. Ví dụ, với $d=3$, chữ a được thay bằng d, b bằng e, …, w thành z, x thành a, y thành b và z thành c.