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

Cho một cây nhị phân gồm ~2\cdot n - 1~ đỉnh được đánh số từ ~1~ đến ~2\cdot n - 1~. Gốc cây là đỉnh ~2\cdot n - 1~. Trên cây, các đỉnh ~1, 2, \ldots, n~ là các đỉnh lá. Các đỉnh ~p~ (~n < p < 2\cdot n~) còn lại đều thoả mãn tính chất sau:

• đỉnh ~p~ có chính xác hai đỉnh con, một đỉnh con bên trái ~a_p~ và một đỉnh con bên phải ~b_p~;

• với cặp đỉnh lá ~u~, ~v~ (~1 \le u, v \le n~) bất kì mà ~a_p~ là tổ tiên^∗ của ~u~ và ~b_p~ là tổ tiên của ~v~, thì ~u < v~.

Với ~1 \le l \le r \le n~, định nghĩa ~f(l, r)~ là số lượng phần tử của tập hợp các đỉnh ~S~ thoả mãn các điều kiện sau:

• với ~l \le u \le r~, tồn tại một tổ tiên của ~u~ trong ~S~;

• với ~1 \le u < l~ hoặc ~r < u \le n~, không tồn tại tổ tiên nào của ~u~ trong ~S~;

• trong tất cả các tập hợp đỉnh thoả mãn hai điều kiện trên, tập ~S~ là tập có ít phần tử nhất.

Bạn được biết số nguyên ~n~, nhưng không biết trước cấu trúc của cây. Bạn cần tương tác với chương trình của ban tổ chức (BTC) để xác định cấu trúc của cây nhị phân. Bạn được phép đưa ra các truy vấn có dạng ~l, r~ (~1 \le l \le r \le n~), và phản hồi bạn nhận được là ~f(l, r)~.

Khi đã xác định được cấu trúc cây, bạn cần đưa ra danh sách các đỉnh con ~a_p~ và ~b_p~ cho các đỉnh ~n < p < 2 \cdot n~. Đáp án của bạn được coi là đúng khi các điều kiện sau thoả mãn:

• bạn đưa ra không quá ~n^2~ truy vấn;

• cấu trúc cây thoả mãn các tính chất đã nêu trên;

• với mọi cặp số ~l, r~ (~1 \le l \le r \le n~), ~f(l, r)~ tính từ cây của bạn phải bằng với ~f(l, r)~ tính từ cây của BTC.

Nếu có nhiều đáp án thoả mãn các điều kiện trên, hãy đưa ra đáp án thoả mãn bất kì.

Trong bài toán này, điểm số bạn nhận được phụ thuộc vào số lượng truy vấn bạn đưa ra. Chi tiết xem thêm phần scoring.

∗ Đỉnh ~p~ được gọi là tổ tiên của ~u~ nếu ~p = u~, hoặc ~p~ không phải là lá và một đỉnh con của ~p~ là tổ tiên của ~u~.

Interaction

Đầu tiên, bạn cần đọc số nguyên ~t~ (~1 \le t \le 150~)  – số test case. Với mỗi test case, quá trình tương tác diễn ra như sau:

• Đầu tiên, hãy đọc vào một số nguyên ~n~ (~2 \le n \le 150~) – số lượng đỉnh lá của cây.

• Để đưa ra truy vấn, hãy in ra ? ~l \ r~ (~1 \le l \le r \le n~), sau đó đọc vào một số nguyên ~f(l, r)~.

• Khi đã xác định được cấu trúc của cây, hãy in ra trên một dòng kí tự !, tiếp đó in ra ~2n - 2~ số nguyên ~a_{n+1}, b_{n+1}, a_{n+2}, b_{n+2}, \ldots, a_{2n-1}, b_{2n-1}~ – danh sách các đỉnh con của các đỉnh ~n + 1, n + 2, \ldots 2 \cdot n - 1~.

  Nếu có nhiều đáp án đúng, hãy in ra đáp án bất kì.

Cây đã được cố định trước quá trình tương tác, và sẽ không thay đổi trong quá trình tương tác.

Dữ liệu vào đảm bảo tổng giá trị ~n~ của các testcase không vượt quá ~150~.

Sau khi in ra một câu lệnh, đừng quên xuống dòng và flush đầu ra chuẩn. Để 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;

• stdout.flush() trong Python;

• xem tài liệu chuẩn đối với các ngôn ngữ khác.

Scoring

Gọi ~q~ là số câu hỏi bạn đưa ra. Điểm số của bạn cho test case như sau:

Điểm số của bộ dữ liệu vào bằng điểm số thấp nhất của các test case. Điểm số của bạn cho bài này bằng điểm số thấp nhất của các bộ dữ liệu vào.

Sample Input 1

2
3

2

1

4

2

2

1

Sample Output 1

? 1 2

? 2 3

! 2 3 1 4

? 1 3

? 2 4

? 1 4

! 1 2 3 4 5 6

Notes

Trong ví dụ đầu tiên, các truy vấn được đưa ra như sau:

• ~f(1, 2) = 2~. Ở đây ~S = \{ 1, 2 \}~

• ~f(2, 3) = 1~. Ở đây ~S = \{ 4 \}~

Trong ví dụ thứ hai, các truy vấn được đưa ra như sau:

• ~f(1, 3) = 2~. Ở đây ~S = \{ 3, 6 \}~

• ~f(2, 4) = 2~. Ở đây ~S = \{ 2, 5 \}~

• ~f(1, 4) = 1~. Ở đây ~S = \{ 7 \}~