Ini adalah soal interaktif.

VegiCat mengetahui sebuah larik $a_1, a_2, \ldots, a_n$, yang setiap elemennya bernilai $0$, $1$, atau $2$. Ia tidak ingin memberi tahu Anda nilainya secara langsung, tetapi Anda dapat mengajukan pertanyaan kepadanya. Pada setiap kueri, Anda memilih dua indeks $i$ dan $j$, lalu VegiCat memberi tahu Anda apakah $a_i > a_j$.

VegiCat meminta Anda mengeluarkan indeks-indeks tersebut dalam urutan tak menurun berdasarkan nilai larik yang bersesuaian. Artinya, carilah sebuah permutasi $p_1, p_2, \ldots, p_n$ dari $1, 2, \ldots, n$ sedemikian sehingga

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

Anda dapat melakukan paling banyak $2n - 3$ kueri pada setiap kasus uji.

Interaktor bersifat adaptif. Ini berarti larik tersebut tidak ditetapkan sejak awal. Interaktor menjamin bahwa selalu terdapat setidaknya satu larik dengan elemen-elemen di $\{0, 1, 2\}$ yang konsisten dengan semua respons yang telah diberikan sejauh ini. Permutasi akhir Anda harus valid untuk setiap larik yang konsisten dengan semua respons.

Masukan

Baris pertama berisi sebuah bilangan bulat $T$ ($1 \le T \le 250$), banyaknya kasus uji. Deskripsi dari setiap kasus uji menyusul.

Setiap kasus uji diawali dengan sebuah bilangan bulat $n$ ($2 \le n \le 500$), panjang larik.

Jumlah $n$ di seluruh kasus uji tidak melebihi $500$.

Interaksi

Untuk mengajukan sebuah kueri, keluarkan satu baris dengan format berikut:

? i j

Di sini, $1 \le i, j \le n$. Setelah setiap kueri, bacalah satu bilangan bulat:

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

Kueri dengan $i = j$ serta kueri berulang diperbolehkan dan tetap dihitung dalam jumlah kueri.

Ketika Anda telah menentukan urutannya, keluarkan satu baris dengan format berikut:

! p_1 p_2 ... p_n

Setiap indeks dari $1$ hingga $n$ harus muncul tepat satu kali. Mencetak jawaban tidak dihitung sebagai kueri.

Jika jawaban Anda benar, lanjutkan ke kasus uji berikutnya dengan membaca nilai $n$-nya, atau hentikan program Anda jika ini adalah kasus uji terakhir. Interaktor tidak mengirimkan konfirmasi terpisah setelah sebuah jawaban.

Setelah mengeluarkan setiap kueri atau jawaban, keluarkan baris baru dan lakukan flush pada penyangga keluaran (output buffer). Untuk melakukan flush pada keluaran, Anda dapat menggunakan:

• fflush(stdout) atau cout.flush() di C/C++;
• System.out.flush() di Java dan Kotlin;
• sys.stdout.flush() di Python.

Jika Anda melakukan kueri yang tidak valid, melebihi batas kueri, atau mencetak jawaban yang salah, Anda akan mendapatkan vonis Wrong Answer. Keluaran yang tidak mengikuti format yang ditentukan juga dinilai Wrong Answer. Dalam kasus-kasus ini, interaktor langsung berhenti tanpa mengirimkan respons kesalahan.

Examples

Input 1

2
3

1

1

2

0

Output 1

? 1 2

? 2 3

! 3 2 1

? 1 2

! 1 2

Note

Pada kasus uji pertama, kueri ? 1 2 dan ? 2 3 keduanya mengembalikan $1$, sehingga $a_1 > a_2 > a_3$. Oleh karena itu, $(3, 2, 1)$ adalah jawaban yang benar.

Pada kasus uji kedua, kueri ? 1 2 mengembalikan $0$, sehingga $a_1 \le a_2$. Oleh karena itu, $(1, 2)$ adalah jawaban yang benar.