هذه مسألة تفاعلية.

يعرف VegiCat مصفوفة $a_1, a_2, \ldots, a_n$، حيث يكون كل عنصر إما $0$ أو $1$ أو $2$. لا يريد إخبارك بقيمها مباشرة، لكن يمكنك طرح أسئلة عليه. في كل استعلام، تختار فهرسين $i$ و $j$، ويخبرك VegiCat ما إذا كان $a_i > a_j$.

يطلب منك VegiCat طباعة الفهارس بترتيب غير متناقص حسب قيم المصفوفة المقابلة. أي أوجد تبديلًا $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. في هذه الحالات، يتوقف المتفاعل دون إرسال رسالة خطأ.

أمثلة

الإدخال 1

2
3

1

1

2

0

الإخراج 1

? 1 2

? 2 3

! 3 2 1

? 1 2

! 1 2

ملاحظة

في حالة الاختبار الأولى، يُعيد الاستعلامان ? 1 2 و ? 2 3 كلاهما $1$، مما يعني أن $a_1 > a_2 > a_3$. وبالتالي فإن $(3, 2, 1)$ إجابة صحيحة.

في حالة الاختبار الثانية، يُعيد الاستعلام ? 1 2 القيمة $0$، مما يعني أن $a_1 \le a_2$. وبالتالي فإن $(1, 2)$ إجابة صحيحة.