Đây là bài toán tương tác.

VegiCat biết một mảng $a_1, a_2, \ldots, a_n$, trong đó mỗi phần tử là $0$, $1$, hoặc $2$. Cậu ấy không muốn cho bạn biết các giá trị của mảng, nhưng bạn có thể đặt câu hỏi cho cậu ấy. Trong mỗi truy vấn, bạn chọn hai chỉ số $i$ và $j$, và VegiCat sẽ cho bạn biết liệu $a_i > a_j$ hay không.

VegiCat yêu cầu bạn in ra các chỉ số theo thứ tự không giảm của các giá trị mảng tương ứng. Tức là, hãy tìm một hoán vị $p_1, p_2, \ldots, p_n$ của $1, 2, \ldots, n$ sao cho

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

Bạn được thực hiện nhiều nhất $2n - 3$ truy vấn trong mỗi bộ dữ liệu.

Trình chấm tương tác có tính thích ứng (adaptive). Điều này có nghĩa là mảng không được cố định trước. Trình chấm đảm bảo rằng luôn tồn tại ít nhất một mảng gồm các phần tử thuộc $\{0, 1, 2\}$ phù hợp với tất cả các câu trả lời đã đưa ra cho đến lúc đó. Hoán vị cuối cùng của bạn phải hợp lệ với mọi mảng phù hợp với tất cả các câu trả lời.

Dữ liệu vào

Dòng đầu tiên chứa một số nguyên $T$ ($1 \le T \le 250$), là số lượng bộ dữ liệu. Mô tả của các bộ dữ liệu theo sau.

Mỗi bộ dữ liệu bắt đầu bằng một số nguyên $n$ ($2 \le n \le 500$), là độ dài của mảng.

Tổng của $n$ trên tất cả các bộ dữ liệu không vượt quá $500$.

Giao tiếp

Để thực hiện một truy vấn, hãy in ra một dòng theo định dạng sau:

? i j

Ở đây, $1 \le i, j \le n$. Sau mỗi truy vấn, hãy đọc một số nguyên:

• $1$, nếu $a_i > a_j$;
• $0$, nếu $a_i \le a_j$.

Các truy vấn với $i = j$ và các truy vấn lặp lại đều được phép và vẫn được tính vào số lần truy vấn.

Khi bạn đã xác định được thứ tự, hãy in ra một dòng theo định dạng sau:

! p_1 p_2 ... p_n

Mỗi chỉ số từ $1$ đến $n$ phải xuất hiện đúng một lần. Việc in ra đáp án không được tính là một truy vấn.

Nếu đáp án của bạn đúng, hãy tiếp tục bộ dữ liệu tiếp theo bằng cách đọc số $n$ của nó, hoặc kết thúc chương trình nếu đây là bộ dữ liệu cuối cùng. Trình chấm không gửi thông báo xác nhận riêng sau khi nhận đáp án.

Sau khi in ra mỗi truy vấn hoặc đáp án, hãy in ký tự xuống dòng và làm rỗng bộ đệm đầu ra (flush). Để làm rỗng bộ đệm đầu ra, bạn có thể dùng:

• fflush(stdout) hoặc cout.flush() trong C/C++;
• System.out.flush() trong Java và Kotlin;
• sys.stdout.flush() trong Python.

Nếu bạn thực hiện truy vấn không hợp lệ, vượt quá giới hạn truy vấn, hoặc in ra đáp án sai, bạn sẽ nhận kết quả Wrong Answer. Đầu ra không tuân theo định dạng quy định cũng bị chấm là Wrong Answer. Trong những trường hợp này, trình chấm sẽ kết thúc ngay mà không gửi phản hồi báo lỗi.

Ví dụ

Dữ liệu vào 1

2
3

1

1

2

0

Dữ liệu ra 1

? 1 2

? 2 3

! 3 2 1

? 1 2

! 1 2

Ghi chú

Ở bộ dữ liệu đầu tiên, các truy vấn ? 1 2 và ? 2 3 đều trả về $1$, suy ra $a_1 > a_2 > a_3$. Do đó, $(3, 2, 1)$ là một đáp án đúng.

Ở bộ dữ liệu thứ hai, truy vấn ? 1 2 trả về $0$, suy ra $a_1 \le a_2$. Do đó, $(1, 2)$ là một đáp án đúng.