شكرًا لعملك الجاد يا عزيزي. لا يعرف Little Cyan Fish كم من كلماته المشفرة يمكن إيصالها، لكنه مع ذلك يشكرك على السير معه إلى هذه النقطة. حدثت أشياء كثيرة جدًا، أشياء عبثية للغاية، وقد تعب Little Cyan Fish، تعب بشدة... في العام الماضي، شعر Little Cyan Fish عدة مرات أنه على وشك إنقاذ نفسه، لكنه في النهاية لم يكن قويًا بما يكفي لقطع الخيوط الملتفة حول جسده. يتخيل Little Cyan Fish دائمًا أنه في ذلك المكان البعيد توجد ذات أخرى له تستطيع رؤية خريطة حياته بوضوح.

— «التوق إلى البعيد» · نهائي المسابقة الصينية العاشرة لبرمجة طلاب الجامعات

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

حسنًا، ربما يمكنك المحاولة لترى مدى صعوبة ذلك. يشعر 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