תודה על העבודה הקשה שלך, יקירי. Little Cyan Fish לא יודע כמה ממילות הקוד שלו ניתן להעביר, אבל עדיין מודה לך על שצעדת עד לנקודה הזו יחד עם Little Cyan Fish. כל כך הרבה דברים, כל כך הרבה דברים אבסורדיים קרו, Little Cyan Fish עייף, עייף מאוד... בשנה החולפת, Little Cyan Fish הרגיש כמה פעמים שהוא עומד להציל את עצמו, אבל בסופו של דבר, הוא לא היה חזק מספיק כדי לחתוך את החוטים שעל גופו. Little Cyan Fish תמיד מדמיין שבמקום הרחוק ההוא, יש עצמי אחר שיכול לראות בבירור את מפת חייו.

— "כמיהה למרחקים" · גמר תחרות התכנות האקדמית ה-10 של סין

זוהי בעיה אינטראקטיבית.

ובכן, אולי תוכל לנסות ולראות עד כמה זה יהיה קשה. Little Cyan Fish מרגיש שחייו הם תמורה בעלת צורה לא ידועה. אנשים תמיד אומרים שהעולם מלא באקראיות, אבל למה ל-Little Cyan Fish תמיד יש כל כך הרבה חוסר מזל...? אהה! אולי האקראיות היא פשוט עד כדי כך עמוקה! לכן, Little Cyan Fish מחליט שהתמורה הזו שלו תיווצר באקראי באופן הבא:

• צור תמורה אקראית $p_1, p_2, \dots, p_n$: נבחרת באקראי בהתפלגות אחידה מבין כל $n!$ התמורות האפשריות של $1$ עד $n$.
• אם $p_1 > p_n$, הפוך את סדר התמורה כולה.

אינך יכול לצפות ישירות במבנה התמורה, אך Little Cyan Fish העניק לך כוח-על: לשאול! בכל פעם, תוכל לשאול באופן אינטראקטיבי מהו ערך המרחק בין שני מספרים בתמורה מודולו $3$. באופן ספציפי, בכל פעם תוכל לבחור שני מספרים $u, v$ ($1 \le u, v \le n$, $u \ne v$), והתמורה תגיד לך את ערך המרחק בין שני המספרים הללו מודולו $3$ (כלומר, תמצא שני אינדקסים $i, j$ המקיימים $p_i = u, p_j = v$, והתמורה תענה $|i - j| \bmod 3$).

כעת, Little Cyan Fish רוצה שתנסה ותראה מה תוכל להשיג. עליך לעזור ל-Little Cyan Fish לקבוע את התמורה הזו בלא יותר מ-$25n$ שאילתות.

קלט

ישנם מספר מקרי בדיקה. השורה הראשונה של הקלט מכילה מספר שלם יחיד $T$ ($1 \le T \le 1000$), המציין את מספר מקרי הבדיקה.

עבור כל מקרה בדיקה, תחילה עליך לקרוא מספר שלם $n$ ($3 \le n \le 10^4$).

פרוטוקול אינטראקציה

לאחר מכן, האינטראקציה מתחילה. באפשרותך לבצע לא יותר מ-$25n$ שאילתות בכל מקרה בדיקה. כדי לבצע שאילתה, עליך להדפיס שורה יחידה ? u v ($1 \le u, v \le n$, $u \ne v$), המתארת שאילתה. לאחר מכן, עליך לקרוא את התוצאה מהקלט הסטנדרטי.

כדי לספק את תשובתך, עליך להדפיס ! p1 p2 ... pn. הפלט שלך חייב לקיים $p_1 < p_n$. הדפסת התשובה לא תיספר במגבלת $25n$ השאילתות. לאחר שתדפיס את התשובה, עליך לקרוא מיד את מקרה הבדיקה הבא, או לצאת מהתוכנית שלך מיד.

לאחר הדפסת שאילתה, אל תשכח להדפיס תו ירידת שורה ולרוקן את זרם הפלט (flush). כדי לעשות זאת, תוכל להשתמש ב-fflush(stdout) או ב-cout.flush() ב-C++, ב-System.out.flush() ב-Java, ב-flush(output) ב-Pascal, וב-stdout.flush() ב-Python.

מובטח כי סכום ה-$n$ על פני כל מקרי הבדיקה אינו עולה על $10^4$.

בבעיה זו, מובטח כי האינטראקטור הוא לא-אדפטיבי (non-adaptive). כלומר, התמורות נקבעות באקראי כפי שתואר בבעיה לפני תהליך האינטראקציה. הן לא ישתנו בהתאם לשאילתות שלך. ישנם בסך הכל $30$ מקרי בדיקה (כולל מקרה הבדיקה לדוגמה).

דוגמה

קלט 1

2
3
2
1
1
4
1
1
1
0
2

פלט 1

? 1 2
? 2 3
? 1 3
! 1 3 2
? 2 3
? 3 1
? 1 4
? 2 4
? 2 1
! 2 3 1 4

הערה

איור 1: Little Cyan Fish ו-<?> ב-<?>, צולם ב-4 במרץ 2026