לאחר התמחות מוצלחת, Bytholomew התקבל לעבודה כמומחה בכיר לאבטחת סייבר. כדי לשמש דוגמה, הוא החליט סוף סוף לפעול לפי עצתו שלו ולהשתמש בשתי סיסמאות שונות לדואר האלקטרוני שלו ולרשת החברתית Facepalm. לרוע המזל, זכירת שתי סיסמאות התבררה כקשה מדי עבורו. בנוסף, הוא לא יכול היה פשוט לרשום את הסיסמאות במקום כלשהו כפי שהן, משום שהדבר היה מנוגד להמלצה אחרת שלו. אך כמומחה לאבטחה, Bytholomew ידע בדיוק מה לעשות. הוא בחר את המספר השלם האהוב עליו $d>0$ ורשם את שתי הסיסמאות מוצפנות בצופן קיסר (1) עם המפתח $d$.

מרוצה מעבודתו, הוא הביט ברשימותיו וגילה את האמת הנוראה: לאחר ההצפנה, הסיסמה הראשונה (של הדואר האלקטרוני) הפכה בדיוק לסיסמה השנייה (של 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.