Terima kasih atas kerja kerasmu, sayang. Little Cyan Fish tidak tahu seberapa banyak kata sandinya yang dapat tersampaikan, namun tetap berterima kasih kepadamu karena telah berjalan sampai ke titik ini bersama Little Cyan Fish. Begitu banyak hal, begitu banyak hal konyol yang terjadi, Little Cyan Fish lelah, sangat lelah... Dalam setahun terakhir, Little Cyan Fish beberapa kali merasa bahwa ia akan menyelamatkan dirinya sendiri, namun pada akhirnya, ia tidak cukup kuat untuk memutus benang-benang di tubuhnya. Little Cyan Fish selalu membayangkan bahwa di tempat yang jauh di sana, ada dirinya yang lain yang dapat melihat peta hidupnya dengan jelas.

— "Longing for the Distance" · Final China Collegiate Programming Contest ke-10

Ini adalah persoalan interaktif.

Yah, mungkin Anda bisa mencoba seberapa sulit persoalan ini nantinya. Little Cyan Fish merasa bahwa hidupnya adalah sebuah permutasi dengan bentuk yang tidak diketahui. Orang-orang selalu berkata bahwa dunia ini penuh dengan keacakan, tetapi mengapa Little Cyan Fish selalu begitu sial...? Aha! Mungkin keacakan memang sedalam ini! Jadi, Little Cyan Fish memutuskan bahwa permutasi miliknya ini akan dibangkitkan secara acak dengan cara berikut:

• Bangkitkan sebuah permutasi acak $p_1, p_2, \dots, p_n$: dipilih secara acak seragam dari seluruh $n!$ kemungkinan permutasi dari $1$ hingga $n$.
• Jika $p_1 > p_n$, maka balikkan seluruh permutasi tersebut.

Anda tidak dapat mengamati struktur permutasi tersebut secara langsung, tetapi Little Cyan Fish telah memberi Anda sebuah kekuatan super: bertanya! Setiap kali, Anda dapat melakukan kueri secara interaktif untuk menanyakan nilai jarak antara dua bilangan pada permutasi tersebut dalam modulo $3$. Secara spesifik, setiap kali Anda dapat memilih dua bilangan $u, v$ ($1 \le u, v \le n$, $u \ne v$), permutasi akan memberi tahu Anda nilai jarak antara kedua bilangan ini dalam modulo $3$ (yaitu, mencari dua indeks $i, j$ yang memenuhi $p_i = u, p_j = v$, permutasi akan menjawab $|i - j| \bmod 3$).

Sekarang, Little Cyan Fish ingin Anda mencoba dan melihat apa yang bisa Anda dapatkan. Anda perlu membantu Little Cyan Fish menentukan permutasi ini dalam paling banyak $25n$ kueri.

Masukan

Terdapat beberapa kasus uji. Baris pertama dari masukan berisi sebuah bilangan bulat $T$ ($1 \le T \le 1000$), yang menyatakan banyaknya kasus uji.

Untuk setiap kasus uji, pertama-tama Anda perlu membaca sebuah bilangan bulat $n$ ($3 \le n \le 10^4$).

Protokol Interaksi

Selanjutnya, interaksi dimulai. Anda dapat melakukan paling banyak $25n$ kueri pada setiap kasus uji. Untuk melakukan sebuah kueri, Anda perlu mencetak satu baris ? u v ($1 \le u, v \le n$, $u \ne v$), yang mendeskripsikan sebuah kueri. Kemudian, Anda perlu membaca hasilnya dari masukan standar.

Untuk memberikan jawaban Anda, Anda perlu mencetak ! p1 p2 ... pn. Keluaran Anda harus memenuhi $p_1 < p_n$. Mencetak jawaban tidak akan dihitung ke dalam batas $25n$ kueri. Setelah Anda mencetak jawaban, Anda harus segera membaca kasus uji berikutnya, atau segera keluar dari program Anda.

Setelah mencetak sebuah kueri, jangan lupa untuk mencetak karakter baris baru (newline) dan melakukan flush pada aliran keluaran. Untuk melakukan ini, Anda dapat menggunakan fflush(stdout) atau cout.flush() di C++, System.out.flush() di Java, flush(output) di Pascal, dan stdout.flush() di Python.

Dijamin bahwa jumlah dari $n$ di semua kasus uji tidak melebihi $10^4$.

Pada persoalan ini, dijamin bahwa interaktor bersifat non-adaptif. Artinya, permutasi-permutasi tersebut ditentukan secara acak sebagaimana dinyatakan dalam soal sebelum proses interaksi dimulai. Permutasi tersebut tidak akan berubah mengikuti kueri Anda. Terdapat total $30$ kasus uji (termasuk kasus uji contoh).

Contoh

Masukan 1

2
3
2
1
1
4
1
1
1
0
2

Keluaran 1

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

Catatan

Gambar 1: Little Cyan Fish & <?> di <?> diambil pada 4 Maret 2026