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

VegiCat יודע מערך $a_1, a_2, \ldots, a_n$, שבו כל איבר הוא $0$, $1$ או $2$. הוא אינו רוצה לגלות לכם את ערכיו, אך תוכלו לשאול אותו שאלות. בכל שאילתה אתם בוחרים שני אינדקסים $i$ ו-$j$, ו-VegiCat אומר לכם האם $a_i > a_j$.

VegiCat מבקש מכם להדפיס את האינדקסים בסדר לא-יורד (nondecreasing) של ערכי המערך המתאימים. כלומר, מצאו תמורה $p_1, p_2, \ldots, p_n$ של $1, 2, \ldots, n$ כך שמתקיים

$$a_{p_1} \le a_{p_2} \le \cdots \le a_{p_n}.$$

ניתן לבצע לכל היותר $2n - 3$ שאילתות בכל מקרה בדיקה.

האינטראקטור הוא אדפטיבי (adaptive). משמעות הדבר היא שהמערך אינו קבוע מראש. האינטראקטור מבטיח שתמיד קיים לפחות מערך אחד שאיבריו מתוך $\{0, 1, 2\}$ העקבי עם כל התשובות שניתנו עד כה. התמורה הסופית שלכם חייבת להיות תקפה עבור כל מערך העקבי עם כל התשובות.

קלט

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

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

סכום ערכי $n$ על פני כל מקרי הבדיקה אינו עולה על $500$.

אינטראקציה

כדי לבצע שאילתה, הדפיסו שורה בפורמט הבא:

? i j

כאן $1 \le i, j \le n$. לאחר כל שאילתה, קראו מספר שלם אחד:

• $1$, אם $a_i > a_j$;
• $0$, אם $a_i \le a_j$.

שאילתות עם $i = j$ ושאילתות חוזרות מותרות ונכללות בספירת השאילתות.

כאשר קבעתם את הסדר, הדפיסו שורה בפורמט הבא:

! p_1 p_2 ... p_n

כל אינדקס מ-$1$ עד $n$ חייב להופיע בדיוק פעם אחת. הדפסת התשובה אינה נספרת כשאילתה.

אם תשובתכם נכונה, המשיכו למקרה הבדיקה הבא על ידי קריאת ה-$n$ שלו, או סיימו את התוכנית אם זה היה מקרה הבדיקה האחרון. האינטראקטור אינו שולח אישור נפרד לאחר תשובה.

לאחר הדפסת כל שאילתה או תשובה, הדפיסו ירידת שורה ורוקנו את חוצץ הפלט (flush). כדי לרוקן את הפלט, ניתן להשתמש ב:

• fflush(stdout) או cout.flush() ב-C/C++;
• System.out.flush() ב-Java וב-Kotlin;
• sys.stdout.flush() ב-Python.

אם תבצעו שאילתה לא חוקית, תחרגו ממגבלת השאילתות או תדפיסו תשובה שגויה, תקבלו פסק דין Wrong Answer. גם פלט שאינו עוקב אחר הפורמט המוגדר יישפט כ-Wrong Answer. במקרים אלו, האינטראקטור מסיים את פעולתו ללא שליחת הודעת שגיאה.

Examples

Input 1

2
3

1

1

2

0

Output 1

? 1 2

? 2 3

! 3 2 1

? 1 2

! 1 2

Note

במקרה הבדיקה הראשון, השאילתות ? 1 2 ו-? 2 3 שתיהן מחזירות $1$, ולכן $a_1 > a_2 > a_3$. לפיכך, $(3, 2, 1)$ היא תשובה נכונה.

במקרה הבדיקה השני, השאילתה ? 1 2 מחזירה $0$, ולכן $a_1 \le a_2$. לפיכך, $(1, 2)$ היא תשובה נכונה.