Vất vả cho em rồi, yêu dấu. Little Cyan Fish không biết mật ngữ của mình có thể truyền tải được bao nhiêu, nhưng vẫn cảm ơn bạn vì đã cùng Little Cyan Fish đi đến chặng đường này. Quá nhiều chuyện, quá nhiều điều phi lý đã xảy ra, Little Cyan Fish mệt rồi, thực sự rất mệt... Trong năm qua, đã vài lần Little Cyan Fish cảm thấy mình sắp tự cứu lấy bản thân, nhưng suy cho cùng, cậu vẫn chưa đủ mạnh mẽ để cắt đứt những sợi dây trói buộc trên cơ thể mình. Little Cyan Fish luôn tưởng tượng rằng ở nơi xa xôi ấy, có một bản ngã khác có thể nhìn thấy rõ tấm bản đồ cuộc đời cậu.

— "Hướng về phương xa" · Chung kết Cuộc thi Lập trình Sinh viên Trung Quốc lần thứ 10

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

Chà, có lẽ bạn có thể thử xem việc này sẽ khó đến mức nào. Little Cyan Fish cảm thấy cuộc đời mình là một hoán vị chưa rõ hình dạng. Người ta vẫn thường nói thế giới đầy rẫy sự ngẫu nhiên, nhưng tại sao Little Cyan Fish lại luôn kém may mắn đến thế...? A ha! Có lẽ sự ngẫu nhiên vốn dĩ深sâu sắc như vậy! Vì thế, Little Cyan Fish quyết định rằng hoán vị này của cậu sẽ được sinh ngẫu nhiên theo cách sau:

• Sinh một hoán vị ngẫu nhiên $p_1, p_2, \dots, p_n$: được chọn ngẫu nhiên đồng đều từ tất cả $n!$ hoán vị có thể có từ $1$ đến $n$.
• Nếu $p_1 > p_n$, thì đảo ngược toàn bộ hoán vị.

Bạn không thể trực tiếp quan sát cấu trúc của hoán vị, nhưng Little Cyan Fish đã ban cho bạn một siêu năng lực: đặt câu hỏi! Mỗi lần, bạn có thể truy vấn tương tác giá trị khoảng cách giữa hai số trong hoán vị theo modulo $3$. Cụ thể, mỗi lần bạn có thể chọn hai số $u, v$ ($1 \le u, v \le n$, $u \ne v$), hoán vị sẽ cho bạn biết giá trị khoảng cách giữa hai số này theo modulo $3$ (tức là tìm hai chỉ số $i, j$ thỏa mãn $p_i = u, p_j = v$, hoán vị sẽ trả lời $|i - j| \bmod 3$).

Bây giờ, Little Cyan Fish muốn bạn thử xem mình có thể thu được gì. Bạn cần giúp Little Cyan Fish xác định hoán vị này trong không quá $25n$ truy vấn.

Dữ liệu vào

Có nhiều bộ test. Dòng đầu tiên của dữ liệu vào chứa một số nguyên duy nhất $T$ ($1 \le T \le 1000$), cho biết số lượng bộ test.

Với mỗi bộ test, trước tiên bạn cần đọc một số nguyên $n$ ($3 \le n \le 10^4$).

Giao thức tương tác

Tiếp theo, quá trình tương tác bắt đầu. Bạn có thể thực hiện không quá $25n$ truy vấn trong mỗi bộ test. Để thực hiện một truy vấn, bạn cần in ra một dòng duy nhất ? u v ($1 \le u, v \le n$, $u \ne v$), mô tả một truy vấn. Sau đó, bạn cần đọc kết quả từ đầu vào chuẩn.

Để đưa ra câu trả lời, bạn cần in ra ! p1 p2 ... pn. Kết quả của bạn phải thỏa mãn $p_1 < p_n$. Việc in ra câu trả lời sẽ không được tính vào giới hạn $25n$ truy vấn. Sau khi in ra câu trả lời, bạn cần đọc bộ test tiếp theo ngay lập tức, hoặc thoát chương trình ngay lập tức.

Sau khi in ra một truy vấn, đừng quên in ký tự xuống dòng và làm rỗng bộ đệm đầu ra (flush). Để làm điều này, bạn có thể sử dụng fflush(stdout) hoặc cout.flush() trong C++, System.out.flush() trong Java, flush(output) trong Pascal, và stdout.flush() trong Python.

Đảm bảo rằng tổng của $n$ trên tất cả các bộ test không vượt quá $10^4$.

Trong bài toán này, đảm bảo rằng trình chấm tương tác là không thích ứng (non-adaptive). Nghĩa là, các hoán vị được xác định ngẫu nhiên như đề bài đã nêu trước quá trình tương tác. Chúng sẽ không thay đổi theo các truy vấn của bạn. Có tổng cộng $30$ test (bao gồm cả test ví dụ).

Ví dụ

Dữ liệu vào 1

2
3
2
1
1
4
1
1
1
0
2

Dữ liệu ra 1

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

Giải thích

Hình 1: Little Cyan Fish & <?> tại <?> chụp vào ngày 4 tháng 3 năm 2026